Publications - Working papers
Please find below working papers of our group. Currently, we list 58 working papers.
In the list are only not published papers present. If you look for a preprint of an already published paper you must look in the "Published papers" section.
If you have problems accessing electronic information, please let us know:
©NOTICE: All working papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
A Local Prime Factor Decomposition Algorithm
Marc Hellmuth
Download
Status: Submitted
Discrete Mathematics
Abstract
This work is concerned with the prime factor decomposition (PFD) of strong product graphs.
A new quasi-linear time algorithm for the PFD with respect to the strong product
for arbitrary, finite, connected graphs is derived.
Moreover, since most graphs are prime although they can have a product-like structure, also known as
approximate graph products, the practical application of the well-known "classical" prime factorization
algorithm is strictly limited. This new PFD algorithm is based on a local approach that covers a graph
by small factorizable subgraphs and then utilizes this information to derive the global factors.
Therefore, we can take advantage of this approach and derive in addition a method for the recognition
of approximate graph products.
Keywords
strong product graph, prime factor decomposition, local covering, backbone, colorcontinuation, S1-condition