Schranken für den minimalen orientierten Durchmesser
Lätsch, Martin (2008) Schranken für den minimalen orientierten Durchmesser. PhD thesis.
Abstract
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 4D. 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: 
PDF
 Published Version
Download (722kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Thesis (PhD) 

Citations:  0 (Google Scholar)  
Uncontrolled Keywords:  digraph oriented diameter dominating set 
Subjects: 

Divisions:  UNSPECIFIED 
Related URLs: 
ZAIK Number:  zaik2008580 

Depositing User:  Martin Lätsch 
Date Deposited:  24 Oct 2008 00:00 
Last Modified:  19 Dec 2011 09:44 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/580 