A polynomial time algorithm for finding the prime factors of cartesian-product graphs

1985/10/01 by Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Cartesian product #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Equivalence (formal languages) #Equivalence relation #Graph #Graph Labeling and Dimension Problems #Mathematics #Prime (order theory) #Prime factor #Product (mathematics) #Time complexity

paper · doi:10.1016/0166-218x(85)90066-6

crossref issued 1985/10/01 · crossref published 1985/10/01 · crossref published-print 1985/10/01 · openalex publication_date 1985/10/01 · crossref created 2002/09/17 · crossref deposited 2019/04/09 · openalex created_date 2025/10/10 · crossref indexed 2026/05/13 · openalex updated_date 2026/06/26

Citations

• Algorithm 97: Shortest path

Cited by

• Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
• Recognizing Cartesian products in linear time
• Cartesian graph factorization at logarithmic cost per edge
• Factoring cardinal product graphs in polynomial time
• Cartesian product of graphs [wikipedia]