Skip to main content

Finding the Prime Factors of Strong Direct Product Graphs in Polynomial Time

New Image

The strong direct product is one of several standard product operators on graphs. McKenzie [Fund. Math. LXX(1971), 59-101] showed that any connected graph has a unique prime factorization under the strong direct product. We give a polynomial-time algorithm for finding this unique factorization, thus settling a question of Nesetril.