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 -