ubl
Local Prime Factor Decomposition
of Approximate Strong Product Graphs
Local Prime Factor Decompositionof Approximate Strong Product Graphs
2010-07-07
[Electronic ed.]
prv
Universitätsbibliothek Leipzig
Universitätsbibliothek Leipzig, Leipzig
Fakultät für Mathematik und Informatik
male
Nordhausen
In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since
most graphs are prime, although they can have a product-like structure.
This work is concerned with the strong graph product. Since strong product graphs G contain
subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to
develop local approaches that cover a graph by factorizable patches and then use this information to
derive the global factors.
First, we investigate the local structure of strong product graphs and introduce the backbone B(G)
of a graph G and the so-called S1-condition. Both concepts play a central role for determining the
prime factors of a strong product graph in a unique way. Then, we discuss several graph classes,
in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear
time prime factorization algorithms. Combining these results, we then derive a new local prime
factorization algorithm for all graphs.
Finally, we discuss approximate graph products. We use the new local factorization algorithm to
derive a method for the recognition of approximate graph products. Furthermore, we evaluate the
performance of this algorithm on a sample of approximate graph products.
500
strong product graph, prime factor decomposition, local covering, backbone, color-continuation, S1-condition
urn:nbn:de:bsz:15-qucosa-38755
Universität Leipzig
dgg
Universität Leipzig, Leipzig
Marc
Hellmuth
Dr. rer. nat
1980-06-25
aut
Peter F.
Stadler
Professor Dr.
dgs
rev
Sandi
Klavžar
Professor Dr.
rev
eng
2010-03-04
2010-04-22
born digital
Marc Hellmuth
marc@bioinf.uni-leipzig.de
doctoral_thesis
pdf der diss auch zu finden auf:
https://www.bioinf.uni-leipzig.de/~marc/Dissertation_MarcHellmuth.pdf