Spelling suggestions: "subject:"ondiscontinuation"" "subject:"futurecontinuation""
1 |
Local Prime Factor Decomposition of Approximate Strong Product GraphsHellmuth, Marc 07 July 2010 (has links) (PDF)
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.
|
2 |
Local Prime Factor Decomposition of Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product GraphsHellmuth, Marc 22 April 2010 (has links)
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.
|
Page generated in 0.0863 seconds