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.

Back to all abstracts