On the Cardinal Product

Publikationen: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

Standard

On the Cardinal Product. / Klöckl, Werner.
2007.

Publikationen: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

Harvard

Bibtex - Download

@phdthesis{e53932511e40442a99f7866832c62ed0,
title = "On the Cardinal Product",
abstract = "The aim of the dissertation are algorithms for the factorization of graphs with respect to the cardinal and the strong product. We develop algorithms for each of these products. The algorithm for the strong product applies Feigenbaum's and Sch{\"a}ffer's polynomial algorithm locally and improves its global complexity. The algorithm for the cardinal product that is presented here is so far the only one that computes the prime factor decomposition of a directed graph with respect to the cardinal product under certain conditions in polynomial time. The proof of the correctness of the algorithm also shows that the prime factorization is unique, which extends the class of directed graphs that are known to have a unique prime factorization. For further generalizations we introduce and investigate a new special class of graphs, so-called R^+_{s,r} - graphs. Our results help to describe the structure of the automorphism group of directed cardinal product graphs. We apply them to the computation of distinguishing numbers of product graphs.",
keywords = "Kardinalprodukt, polynomialer Automorphismen, starkes Produkt, Primfaktorzerlegung, Algorithmus, Unterscheidungszahl, cardinal product, polynomial automorphisms, prime factorization algorithm, distinguishing number",
author = "Werner Kl{\"o}ckl",
note = "no embargo",
year = "2007",
language = "English",

}

RIS (suitable for import to EndNote) - Download

TY - BOOK

T1 - On the Cardinal Product

AU - Klöckl, Werner

N1 - no embargo

PY - 2007

Y1 - 2007

N2 - The aim of the dissertation are algorithms for the factorization of graphs with respect to the cardinal and the strong product. We develop algorithms for each of these products. The algorithm for the strong product applies Feigenbaum's and Schäffer's polynomial algorithm locally and improves its global complexity. The algorithm for the cardinal product that is presented here is so far the only one that computes the prime factor decomposition of a directed graph with respect to the cardinal product under certain conditions in polynomial time. The proof of the correctness of the algorithm also shows that the prime factorization is unique, which extends the class of directed graphs that are known to have a unique prime factorization. For further generalizations we introduce and investigate a new special class of graphs, so-called R^+_{s,r} - graphs. Our results help to describe the structure of the automorphism group of directed cardinal product graphs. We apply them to the computation of distinguishing numbers of product graphs.

AB - The aim of the dissertation are algorithms for the factorization of graphs with respect to the cardinal and the strong product. We develop algorithms for each of these products. The algorithm for the strong product applies Feigenbaum's and Schäffer's polynomial algorithm locally and improves its global complexity. The algorithm for the cardinal product that is presented here is so far the only one that computes the prime factor decomposition of a directed graph with respect to the cardinal product under certain conditions in polynomial time. The proof of the correctness of the algorithm also shows that the prime factorization is unique, which extends the class of directed graphs that are known to have a unique prime factorization. For further generalizations we introduce and investigate a new special class of graphs, so-called R^+_{s,r} - graphs. Our results help to describe the structure of the automorphism group of directed cardinal product graphs. We apply them to the computation of distinguishing numbers of product graphs.

KW - Kardinalprodukt

KW - polynomialer Automorphismen

KW - starkes Produkt

KW - Primfaktorzerlegung

KW - Algorithmus

KW - Unterscheidungszahl

KW - cardinal product

KW - polynomial automorphisms

KW - prime factorization algorithm

KW - distinguishing number

M3 - Doctoral Thesis

ER -