Factoring Cartesian-product graphs 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. Factoring Cartesian-product graphs at logarithmic cost per edge. In Proc. MPS Conf. Integer Programming and Combinatorial Optimization IPCO'90, pages 29-44, Waterloo, Canada, 1990. [IIG-Report-Series 287, TU Graz, Austria, 1990].