# Cartesian graph factorization at logarithmic cost per edge

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

### Abstract:

Let be a connected graph with vertices and edges. We develop an algorithm that finds the prime factors of with respect to Cartesian multiplication in time and space. This shows that factoring 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.