Cartesian S-prime Graphs and a New Local PFD Algorithm w.r.t. the Strong Product
Presented by Dr. Marc HELLMUTH
Type: Oral presentation
Track: General session
A graph is said to be S-prime if, whenever it is a subgraph of a nontrivial Cartesian product graph, it is a subgraph of one of the factors. A diagonalized Cartesian product is obtained from a Cartesian product graph by connecting two vertices of maximal distance by an additional edge. We show that a diagonalized product of S-prime graphs is again S-prime. This in turn, solves a fundamental, the so-called color-continuation problem, that emerges in the context of a new quasi-linear time algorithm for the prime factor decomposition (PFD) with respect to the strong product. We will shortly introduce this new PFD algorithm and explain how this approach can be used in order to derive in addition a method for the recognition of so-called approximate graph products.