A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct...A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
Let G be a primitive strongly regular graph of order n and A is adjacency matrix. In this paper we first associate to A a real 3-dimensional Euclidean Jordan algebra? with rank three spanned by In and the natural powe...Let G be a primitive strongly regular graph of order n and A is adjacency matrix. In this paper we first associate to A a real 3-dimensional Euclidean Jordan algebra? with rank three spanned by In and the natural powers of A that is a subalgebra of the Euclidean Jordan algebra of symmetric matrix of order n. Next we consider a basis? that is a Jordan frame of . Finally, by an algebraic asymptotic analysis of the second spectral decomposition of some Hadamard series associated to A we establish some inequalities over the spectra and over the parameters of a strongly regular graph.展开更多
We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility c...We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.展开更多
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be ...We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .展开更多
To properly compute the ontological similarity, an ontological similarity network-based reasoning framework is proposed. It structurally integrates extension-based approach, intension-based approach, the similarity ne...To properly compute the ontological similarity, an ontological similarity network-based reasoning framework is proposed. It structurally integrates extension-based approach, intension-based approach, the similarity network-based reasoning to exploit the implicit similarity, and the feedback from the context to validate the similarity measures. A new similarity measure is also presented to construct concept similarity network, which scales the similarity using the relative depth of the least common super-concept between any two concepts. Subsequently, the graph theory, instead of predefined knowledge rules, is applied to perform the similarity network-based reasoning such that the knowledge acquisition can be avoided. The framework has been applied to text categorization and visualization of high dimensional data. Theory analysis and the experimental results validate the proposed framework.展开更多
文摘A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.
文摘The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
文摘Let G be a primitive strongly regular graph of order n and A is adjacency matrix. In this paper we first associate to A a real 3-dimensional Euclidean Jordan algebra? with rank three spanned by In and the natural powers of A that is a subalgebra of the Euclidean Jordan algebra of symmetric matrix of order n. Next we consider a basis? that is a Jordan frame of . Finally, by an algebraic asymptotic analysis of the second spectral decomposition of some Hadamard series associated to A we establish some inequalities over the spectra and over the parameters of a strongly regular graph.
基金supported by the European Regional Development Fund through the program COMPETEby the Portuguese Government through the FCT—Fundacao para a Ciencia e a Tecnologia under the project PEst—C/MAT/UI0144/2013+1 种基金partially supported by Portuguese Funds trough CIDMA—Center for Research and development in Mathematics and Applications,Department of Mathematics,University of Aveiro,3810-193,Aveiro,Portugalthe Portuguese Foundation for Science and Technology(FCT-Fundacao para a Ciencia e Tecnologia),within Project PEst-OE/MAT/UI4106/2014
文摘We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.
文摘We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .
基金The National Natural Science Foundation of China(No.60003019).
文摘To properly compute the ontological similarity, an ontological similarity network-based reasoning framework is proposed. It structurally integrates extension-based approach, intension-based approach, the similarity network-based reasoning to exploit the implicit similarity, and the feedback from the context to validate the similarity measures. A new similarity measure is also presented to construct concept similarity network, which scales the similarity using the relative depth of the least common super-concept between any two concepts. Subsequently, the graph theory, instead of predefined knowledge rules, is applied to perform the similarity network-based reasoning such that the knowledge acquisition can be avoided. The framework has been applied to text categorization and visualization of high dimensional data. Theory analysis and the experimental results validate the proposed framework.
