Return to search

Local Prime Factor Decomposition of Approximate Strong Product Graphs

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:15-qucosa-38755
Date07 July 2010
CreatorsHellmuth, Marc
ContributorsUniversität Leipzig, Fakultät für Mathematik und Informatik, Professor Dr. Peter F. Stadler, Professor Dr. Peter F. Stadler, Professor Dr. Sandi Klavžar
PublisherUniversitätsbibliothek Leipzig
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:doctoralThesis
Formatapplication/pdf

Page generated in 0.002 seconds