A polynomial time algorithm for finding the prime factors of Cartesian- product graphs. (English) Zbl 0579.68028

Summary: We consider the computational complexity of recognizing connected cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.


68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)


Algorithm 97
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] J. Feigenbaum and A.A. Schäffer, Recognizing composite graphs is equivalent to testing graph isomorphism, SIAM J. Comput., to appear. · Zbl 0602.68033
[3] Floyd, R.W., Algorithm 97: shortest path, Cacm, 5, 345, (1962)
[4] Graham, R.L.; Winkler, P., On isometric embeddings of graphs, Trans. AMS, 288, 527-536, (1985) · Zbl 0576.05017
[5] Sabidussi, G., Graph multiplication, Math. Z., 72, 446-457, (1960) · Zbl 0093.37603
[6] Sims, J.; Holton, D.A., Stability of Cartesian products, J. combin. theory, series B, 25, 258-282, (1978) · Zbl 0405.05052
[7] Tarjan, R.E., Efficiency of a good but not linear set union algorithm, Jacm, 22, 215-225, (1975) · Zbl 0307.68029
[8] P. Winkler, Private communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.