Schranken für den minimalen orientierten Durchmesser

Lätsch, Martin (2008) Schranken für den minimalen orientierten Durchmesser. PhD thesis.


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 diam_{min}(G) of an undirected graph and the size gamma(G) of a minimal dominating set, which improves an upper bound discovered by Fomin et al. We show if G is a strongly connected graph, then: diam_{min}(G)leq 4gamma(G). Furthermore, if we have a graph G and a dominating set D , not necessarily a minimal dominating set of G , we show how to construct an orientation H of G in polynomial time fulfilling diam(H)leq 4|D|. Furthermore, we determine the exact upper bound for {C_3,C_4} -free graphs. If G is a strongly connected {C_3,C_4} -free graph, then the following holds: diam_{min}(G)leq 3gamma(G)+1. We consider bidirected graphs and characterize undirected graphs that allow a strongly connected bidirection. We show, that for those graphs a bidirected orientation ar{H} exist with diam(ar{H})leq 10gamma(ar{H})-5 .

Download: [img] PDF - Published Version
Download (722kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2008-580
Depositing User: Martin Lätsch
Date Deposited: 24 Oct 2008 00:00
Last Modified: 19 Dec 2011 09:44