Cartesian graph factorization at logarithmic cost per edge

F. Aurenhammer, J. Hagauer, and W. Imrich

Abstract:

Let $G$ be a connected graph with $n$ vertices and $m$ edges. We develop an algorithm that finds the prime factors of $G$ with respect to Cartesian multiplication in $O(m \log n)$ time and $O(m)$ space. This shows that factoring $G$ is at most as costly as sorting its edges. The algorithm gains its efficiency and practicality from using only basic properties of product graphs and simple data structures.



Reference: F. Aurenhammer, J. Hagauer, and W. Imrich. Cartesian graph factorization at logarithmic cost per edge. Computational Complexity, 2:331-349, 1992.