- AutorIn
- Dr. rer. nat Marc Hellmuth
- Titel
- Local Prime Factor Decomposition of Approximate Strong Product Graphs
- Untertitel
- Local Prime Factor Decompositionof Approximate Strong Product Graphs
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa-38755
- Datum der Einreichung
- 04.03.2010
- Datum der Verteidigung
- 22.04.2010
- Abstract (EN)
- 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.
- Freie Schlagwörter (EN)
- strong product graph, prime factor decomposition, local covering, backbone, color-continuation, S1-condition
- Klassifikation (DDC)
- 500
- GutachterIn
- Professor Dr. Peter F. Stadler
- Professor Dr. Sandi Klavžar
- BetreuerIn
- Professor Dr. Peter F. Stadler
- Den akademischen Grad verleihende / prüfende Institution
- Universität Leipzig, Leipzig
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa-38755
- Veröffentlichungsdatum Qucosa
- 07.07.2010
- Dokumenttyp
- Dissertation
- Sprache des Dokumentes
- Englisch