Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Linear-Time Algorithms for Tree Root Problems
verfasst von : Maw-Shang Chang, Ming-Tat Ko, Hsueh-I Lu
Erschienen in: Algorithm Theory – SWAT 2006
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
Let
T
be a tree on a set
V
of nodes. The
p-th power
T
p
of
T
is the graph on
V
such that any two nodes
u
and
w
of
V
are adjacent in
T
p
if and only if the distance of
u
and
w
in
T
is at most
p
. Given an
n
-node
m
-edge graph
G
and a positive integer
p
, the
p-th tree root problem
asks for a tree
T
, if any, such that
G
=
T
p
. Given a graph
G
, the
tree root problem
asks for a positive integer
p
and a tree
T
, if any, such that
G
=
T
p
. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in
O
(
n
3
) (respectively,
O
(
n
4
)) time. In this paper, we give
O
(
n
+
m
)-time algorithms for both problems.