Advertisement
Published in:
2011 | OriginalPaper | Chapter
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
Authors : Feodor F. Dragan, Ekkehard Köhler
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A spanning tree
T
of a graph
G
is called a
tree t-spanner
of
G
if the distance between every pair of vertices in
T
is at most
t
times their distance in
G
. In this paper, we present an algorithm which constructs for an
n
-vertex
m
-edge unweighted graph
G
: (1) a tree
$(2\lfloor\log_2 n\rfloor)$
-spanner in
O
(
m
log
n
) time, if
G
is a chordal graph; (2) a tree
$(2\rho\lfloor\log_2 n\rfloor)$
-spanner in
O
(
mn
log
2
n
) time or a tree
$(12\rho\lfloor\log_2 n\rfloor)$
-spanner in
O
(
m
log
n
) time, if
G
is a graph admitting a Robertson-Seymour’s tree-decomposition with bags of radius at most
ρ
in
G
; and (3) a tree
$(2\lceil{t/2}\rceil\lfloor\log_2 n\rfloor)$
-spanner in
O
(
mn
log
2
n
) time or a tree
$(6t\lfloor\log_2 n\rfloor)$
-spanner in
O
(
m
log
n
) time, if
G
is an arbitrary graph admitting a tree
t
-spanner. For the latter result we use a new necessary condition for a graph to have a tree
t
-spanner: if a graph
G
has a tree
t
-spanner, then
G
admits a Robertson-Seymour’s tree-decomposition with bags of radius at most ⌈
t
/2⌉ in
G
.