Bounds for the minimum oriented diameter

Titelangaben

Kurz, Sascha ; Lätsch, Martin:
Bounds for the minimum oriented diameter.
Bayreuth , 2008

Volltext

	Format: PDF Name: oriented_diameter.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
	Download (271kB)

Abstract

We consider the problem of finding an orientation with minimum diameter of a connected bridgeless graph. Fomin et. al. discovered a relation between the minimum oriented diameter an the size of a minimal dominating set. We improve their upper bound.

Abstract in weiterer Sprache

Wir betrachten das Problem eine Orientierung eines ungerichteten Graphen mit minimalem Durchmesser zu finden. Fomin entdeckte einen Zusammenhang zwischen der kardinalität einer kleinsten dominierenden Menge und eben diesem minimalen orientierten Durchmesser. Wir verbessern die dort gefundene obere Schranke.