Universität zu Köln

Schranken für den minimalen orientierten Durchmesser

Lätsch, Martin (2008) Schranken für den minimalen orientierten Durchmesser. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
Download (705Kb) | Preview

    Abstract

    Wir betrachten in dieser Arbeit das Problem, die Kanten eines Graphen so zu orientieren, dass der Durchmesser des gerichteten Graphen minimal ist. Wir geben eine Schranke für den minimalen orientierten Durchmesser in Abhängigkeit der Kardinalität einer kleinsten dominierenden Menge an. Weiter zeigen wir, wie bei gegebener dominierender Menge eine Orientierung eines Graphen konstruiert werden kann, so dass der Durchmesser der Orientierung kleiner gleich dem Vierfachen der Kardinalität der dominierenden Menge ist. Für die Klasse der Graphen, die weder einen Kreis der Länge drei noch einen Kreis der Länge vier enthalten, zeigen wir eine scharfe Schranke für den minimalen orientierten Durchmesser in Abhängigkeit der Dominanzzahl. In einem weiteren Kapitel betrachten wir bigerichtete Graphen. Wir charakterisieren die Klasse der bigerichteten Graphen, für die eine stark zusammenhängende bigerichtete Orientierung existiert und geben eine Schranke für den minimalen bigerichteten Durchmesser in Abhängigkeit der Kardinalität einer kleinsten dominierenden Menge an.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    In this thesis, we consider the problem of finding an orientation of an undirected graph with minimal diameter. We show a relation between the minimum oriented diameter of an undirected graph and the size of a minimal dominating set. Furthermore, if we have a graph and a dominating set, not necessarily a minimal dominating set, we show how to construct an orientation in polynomial time, such that the diameter of the orientation is less or equal to four times the size of the dominating set. Furthermore, we determine the exact upper bound for graphs without cycles of length three and four. We consider bidirected graphs and characterize undirected graphs that allow a strongly connected bidirection. For those graphs we show an upper bound for the bidirected diameter, which depends on the size of a minimal dominating set.English
    Creators:
    CreatorsEmail
    Lätsch, Martinlaetsch@zpr.uni-koeln.de
    URN: urn:nbn:de:hbz:38-25102
    Subjects: Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    Digraph, orientierter Durchmesser, Dominanzzahl, bigerichteter GraphGerman
    Digraph, oriented diameter, dominating set, bidirected graphEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Mathematisches Institut
    Language: German
    Date: 2008
    Date Type: Completion
    Date of oral exam: 16 October 2008
    Full Text Status: Public
    Date Deposited: 15 Dec 2008 12:19:15
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2510

    Actions (login required)

    View Item