Publications - Published papers

Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (access) is restricted to our local network and chosen collaborators. If you have problems accessing electronic information, please let us know:

©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.

Local algorithms for the prime factorization of strong product graphs

Marc Hellmuth, Wilfried Imrich, Werner Klöckl, Peter F. Stadler


PREPRINT 09-018: [ PDF ]
[ Publishers's page ]  paperID

Status: Published

Mathematics in Computer Science: DOI 10.1007/s11786-009-0073-y


The practical application of graph prime factorization algorithms is limited in practise 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.


strong product graphs, prime factorization, local covering, backbone