Factoring Cartesian-product graphs at logarithmic cost per edge
F. Aurenhammer, J. Hagauer, and W. Imrich
be a connected graph with
edges. We develop an
algorithm that finds the prime factors of
with respect to Cartesian
space. This shows that
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].