dissertation · Qucosa (Saxon State and University Library Dresden) · 2010

Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs

Hellmuth, Marc

Cited by 0Open access

Abstract

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\nmost graphs are prime, although they can have a product-like structure.\nThis work is concerned with the strong graph product. Since strong product graphs G contain\nsubgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to\ndevelop local approaches that cover a graph by factorizable patches and then use this information to\nderive the global factors.\nFirst, we investigate the local structure of strong product graphs and introduce the backbone B(G)\nof a graph G and the so-called S1-condition. Both concepts play a central role for determining the\nprime factors of a strong product graph in a unique way. Then, we discuss several graph classes,\nin detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear\ntime prime factorization algorithms. Combining these results, we then derive a new local prime\nfactorization algorithm for all graphs.\nFinally, we discuss approximate graph products. We use the new local factorization algorithm to\nderive a method for the recognition of approximate graph products. Furthermore, we evaluate the\nperformance of this algorithm on a sample of approximate graph products.

Cite this paper

APA 7

Hellmuth, M. (2010). Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs. Qucosa (Saxon State and University Library Dresden).

MLA 9

Hellmuth, Marc. “Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs.” Qucosa (Saxon State and University Library Dresden), 2010.

Chicago

Hellmuth, Marc. 2010. “Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs.” Qucosa (Saxon State and University Library Dresden).

Harvard

Hellmuth, M. (2010) ‘Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs’, Qucosa (Saxon State and University Library Dresden).

BibTeX

@phdthesis{hellmuth2010local,
  title = {{Local Prime Factor Decomposition\nof Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs}},
  author = {Hellmuth, Marc},
  school = {Qucosa (Saxon State and University Library Dresden)},
  year = {2010}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.