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 (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) 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
Download
Status: Published
Mathematics in Computer Science: DOI 10.1007/s11786-009-0073-y
Abstract
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.
Keywords
strong product graphs, prime factorization, local covering, backbone