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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:11033 |
| Date | 22 April 2010 |
| Creators | Hellmuth, Marc |
| Contributors | Stadler, Peter F., Klavžar, Sandi, Universität Leipzig |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds