TY - GEN

T1 - On graph powers for leaf-labeled trees

AU - Nishimura, Naomi

AU - Ragde, Prabhakar

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - We extend the well-studied concept of a graph power to that of a k-leaf power G of a tree T: G is formed by creating a node for each leaf in the tree and an edge between a pair of nodes if and only if the associated leaves are connected by a path of length at most k. By discov-ering hidden combinatorial structure of cliques and neighbourhoods, we have developed polynomial-time algorithms that, for k = 3 and k = 4, identify whether or not a given graph G is a k-leaf power of a tree T, and if so, produce a tree T for which G is a k-leaf power. We believe that our structural results will form the basis of a solution for more general k. The general problem of inferring hidden tree structure on the basis of leaf relationships shows up in several areas of application.

AB - We extend the well-studied concept of a graph power to that of a k-leaf power G of a tree T: G is formed by creating a node for each leaf in the tree and an edge between a pair of nodes if and only if the associated leaves are connected by a path of length at most k. By discov-ering hidden combinatorial structure of cliques and neighbourhoods, we have developed polynomial-time algorithms that, for k = 3 and k = 4, identify whether or not a given graph G is a k-leaf power of a tree T, and if so, produce a tree T for which G is a k-leaf power. We believe that our structural results will form the basis of a solution for more general k. The general problem of inferring hidden tree structure on the basis of leaf relationships shows up in several areas of application.

UR - http://www.scopus.com/inward/record.url?scp=0141430455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0141430455&partnerID=8YFLogxK

U2 - 10.1007/3-540-44985-X

DO - 10.1007/3-540-44985-X

M3 - Conference contribution

AN - SCOPUS:0141430455

SN - 3540676902

SN - 9783540676904

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 125

EP - 138

BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings

A2 - Halldórsson, Magnús M.

PB - Springer Verlag

T2 - 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000

Y2 - 5 July 2000 through 7 July 2000

ER -