Local Algorithms for the Prime Factorization of Strong Product Graphs

摘要

The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data. A first step towards error-tolerant “approximate” prime factorization, is the development of local approaches that cover the graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product. To this end we introduce the backbone $mathbb{B} (G)$ for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors.