Hellmuth, M.M.HellmuthImrich, W.W.ImrichKlöckl, W.W.KlöcklStadler, P.F.P.F.Stadler2022-03-042022-03-042009https://publica.fraunhofer.de/handle/publica/22103410.1007/s11786-009-0073-yThe 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 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.en610journal article