# Another approach to the linear algorithm for the prime factor decomposition of Cartesian product

###
Iztok Peterin

FEECS, University of Maribor and IMFM Ljubljana

PDF

**Minisymposium:**
GRAPH PRODUCTS

**Content:**
In [Discrete Math. 307 (2007) 472--483] a linear algorithm for the prime factor decomposition of a graph with respect to Cartesian product is presented. Hence the paper establishes the best possible complexity for this important fundamental problem. Unfortunately this algorithm has a big constant and its linearity become visible only for very big graphs. This fact is due to generating lines of adjacency matrix during edge labeling procedure of the algorithm. We present a variant of this algorithm where we can completely avoid adjacency matrix. This
is possible by changing the order of vertices that are scanned, which is not a BFS order anymore as in [Discrete Math. 307 (2007) 472--483].
It seems that this approach will have some influence in recognizing approximate Cartesian products as well as to find a fast prime factor decomposition of a graph with respect to the strong product.