Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Collective Tree 1-Spanners for Interval Graphs
verfasst von : Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we study the existence of a small set
$\mathcal{T}$
of spanning trees that collectively “1-span” an interval graph
G
. In particular, for any pair of vertices
u
,
v
we require a tree
$T \in \mathcal{T}$
such that the distance between
u
and
v
in
T
is at most one more than their distance in
G
. We show that:
– there is no constant size set of collective tree 1-spanners for interval graphs (even unit interval graphs),
– interval graph
G
has a set of collective tree 1-spanners of size
O
(log
D
), where
D
is the diameter of
G
,
– interval graphs have a 1-spanner with fewer than 2
n
– 2 edges.
Furthermore, at the end of the paper we state other results on collective tree c-spanners for
c
> 1 and other more general graph classes.