Finding the prime factors of strong direct product graphs in polynomial time

DOI10.1016/0012-365X(92)90280-SzbMath0786.68076MaRDI QIDQ686286

Joan Feigenbaum, Alejandro A. Schäffer

Publication date: 14 October 1993

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

zbMATH Keywords

polynomial complexitydecomposition algorithmstrong direct product of graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Strong products of Kneser graphs, On the chromatic number of the lexicographic product and the Cartesian sum of graphs, Edge-transitive products, Weak reconstruction of strong product graphs, Coloring graph products---a survey, On some metric properties of direct-co-direct product, Unnamed Item, Robust Factorizations and Colorings of Tensor Graphs, Strong products of hypergraphs: unique prime factorization theorems and algorithms, Recognizing triangulated Cartesian graph products, On the Cartesian skeleton and the factorization of the strong product of digraphs, Unnamed Item, Computing equivalence classes among the edges of a graph with applications, Direct product primality testing of graphs is GI-hard, A local prime factor decomposition algorithm, Asymmetric colorings of products of graphs and digraphs, NZ-flows in strong products of graphs, Strong products of \(\chi\)-critical graphs, Approximate graph products, Unnamed Item, Unnamed Item, Graphs S(n, k) and a Variant of the Tower of Hanoi Problem, Factoring cardinal product graphs in polynomial time

Cites Work

• Factoring a graph in polynomial time
• Computing equivalence classes among the edges of a graph with applications
• A note on Winkler's algorithm for factoring a connected graph
• Prefibers and the cartesian product of metric spaces
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Strict refinement for graphs and digraphs
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Cartesian graph factorization at logarithmic cost per edge
• On the cancellation law among finite relational structures
• Das lexikographische Produkt gerichteter Graphen. (The lexicographic product of directed graphs)
• The Kronecker Product of Graphs
• Retracts of hypercubes
• Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
• Product graph representations
• The Categorical Product of Graphs
• Operations with structures
• Cardinal multiplication of structures with a reflexive relation
• Unnamed Item
• Unnamed Item
• Unnamed Item