Local Algorithms for the Prime Factorization of St

Authors: Marc Hellmuth Wilfried Imrich Werner Klöckl Peter F Stadler

Publish Date: 2009/12/07

Volume: 2, Issue: 4, Pages: 653-682

PDF Link

Abstract

The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data A first step towards errortolerant “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 quasilinear algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product To this end we introduce the backbone mathbbB G for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factorsThis article is published under an open access license Please check the Copyright Information section for details of this license and what reuse is permitted If your intended use exceeds what is permitted by the license or if you are unable to locate the licence and reuse information please contact the Rights and Permissions team

Keywords: