Linear-Time Algorithms for Tree Root Problems
Journal
Algorithmica
Journal Volume
71
Journal Issue
2
Pages
471-495
Date Issued
2015
Author(s)
Chang, M.-S.
Ko, M.-T.
HSUEH-I LU
Abstract
Let T be a tree on a set V of nodes. The p-th powerTp of T is the graph on V such that any two nodes u and w of V are adjacent in Tp 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=Tp. Given an n-node m-edge graph G, the tree root problem asks for a positive integer p and a tree T, if any, such that G=Tp. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O(n3) (respectively, O(n4)) time. In this paper, we give O(n+m)-time algorithms for both problems.
Type
journal article