Factoring cardinal product graphs in polynomial time

DOI10.1016/S0012-365X(98)00069-7zbMath0955.68089MaRDI QIDQ1584444

Wilfried Imrich

Publication date: 2 November 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmconnected nonbipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Some properties on the tensor product of graphs obtained by monogenic semigroups, Distance formula for direct-co-direct product in the case of disconnected factors, A prime factor theorem for bipartite graphs, Some properties on the lexicographic product of graphs obtained by monogenic semigroups, An almost complete description of perfect codes in direct products of cycles, A Heuristic for Direct Product Graph Decomposition, On some metric properties of direct-co-direct product, Exact-2-relation graphs, Robust Factorizations and Colorings of Tensor Graphs, Recognizing triangulated Cartesian graph products, On idomatic partitions of direct products of complete graphs, On the Cartesian skeleton and the factorization of the strong product of digraphs, A METHOD FOR FINDING AGGREGATED REPRESENTATIONS OF LINEAR DYNAMICAL SYSTEMS, Direct product primality testing of graphs is GI-hard, Characterizing \(r\)-perfect codes in direct products of two and three cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring a graph in polynomial time
• Finding the prime factors of strong direct product graphs in polynomial time
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Minimum dimension embedding of finite metric spaces
• Cartesian graph factorization at logarithmic cost per edge
• Associative products of graphs
• On the complexity of recognizing Hamming graphs and related classes of graphs
• On the weak reconstruction of Cartesian-product graphs
• Über das schwache Kartesische Produkt von Graphen
• The Kronecker Product of Graphs
• On Isometric Embeddings of Graphs
• Product graph representations
• Isomorphic components of Kronecker product of bipartite graphs
• The Categorical Product of Graphs
• The Automorphism Group of a Product of Graphs
• Cardinal multiplication of structures with a reflexive relation
• Metric Spaces and Positive Definite Functions