Cited By
View all- Eppstein DHavvaei E(2020)Parameterized Leaf Power Recognition via Embedding into Graph ProductsAlgorithmica10.1007/s00453-020-00720-882:8(2337-2359)Online publication date: 29-May-2020
Linear-Time Algorithms for Tree Root Problems
Abstract
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 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=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.
References
[1]
Agnarsson, G., Halldórsson, M.M.: Coloring powers of planar graphs. SIAM J. Discrete Math. 16(4), 651---662 (2003)
[2]
Agnarsson, G., Halldórsson, M.M.: On colorings of squares of outerplanar graphs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 244---253 (2004)
[3]
Agnarsson, G., Halldórsson, M.M.: Strongly simplicial vertices of powers of trees. Discrete Math. 307(21), 2647---2652 (2007)
[4]
Alon, N., Lubetzky, E.: Graph powers, Delsarte, Hoffman, Ramsey, and Shannon. SIAM J. Discrete Math. 21(2), 329---348 (2007)
[5]
Alon, N., Lubetzky, E.: Independent sets in tensor graph powers. J. Graph Theory 54(1), 73---87 (2007)
[6]
Alon, N., Mohar, B.: The chromatic number of graph powers. Comb. Probab. Comput. 11(1), 1---10 (2002)
[7]
Brandstädt, A., Hundt, C., Mancini, F., Wagner, P.: Rooted directed path graphs are leaf powers. Discrete Math. 310(4), 897---910 (2010)
[8]
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. SIAM, Philadelphia (1999)
[9]
Buneman, P.: Characterization of rigid circuit graphs. Discrete Math. 9, 205---212 (1974)
[10]
Chandran, L.S., Grandoni, F.: A linear time algorithm to list the minimal separators of chordal graphs. Discrete Math. 306, 351---358 (2006)
[11]
Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear-time algorithms for tree root problems. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, pp. 411---422 (2006)
[12]
Chebikin, D.: Graph powers and k-ordered Hamiltonicity. Discrete Math. 308(15), 3220---3229 (2008)
[13]
Chen, Z.-Z., Jiang, T., Lin, G.: Computing phylogenetic roots with bounded degrees and errors. SIAM J. Comput. 32(4), 864---879 (2003)
[14]
Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comput. 34(4), 924---945 (2005)
[15]
DeVos, M., McDonald, J., Scheide, D.: Average degree in graph powers. J. Graph Theory 72(1), 7---18 (2013)
[16]
Dinur, I., Friedgut, E., Regev, O.: Independent sets in graph powers are almost contained in juntas. Geom. Funct. Anal. 18(1), 77---97 (2008)
[17]
Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hamb. 25, 71---76 (1961)
[18]
Dom, M., Guo, J., Hüffner, F., Niedermeier, R.: Closest 4-leaf power is fixed-parameter tractable. Discrete Appl. Math. 156(18), 3345---3361 (2008)
[19]
Dvořák, Z., Král', D., Nejedlý, P., ¿krekovski, R.: Coloring squares of planar graphs with girth six. Eur. J. Comb. 29(4), 838---849 (2008)
[20]
Escalante, F., Montejano, L., Rojano, T.: Characterization of n-path graphs and of graphs having nth root. J. Comb. Theory, Ser. B 16, 282---289 (1974)
[21]
Flotow, C.: Graphs whose powers are chordal and graphs whose powers are interval graphs. J. Graph Theory 24(4), 323---330 (1997)
[22]
Gavril, F.: The intersection graphs of subtrees in trees are exactly chordal graphs. J. Comb. Theory, Ser. B 16, 47---56 (1974)
[23]
Geller, D.P.: The square root of a digraph. J. Comb. Theory 5, 320---321 (1968)
[24]
Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. North-Holland, Amsterdam (2004)
[25]
Gupta, S.K., Singh, A.: On tree roots of graphs. Int. J. Comput. Math. 73, 157---166 (1999)
[26]
Harary, F., Karp, R.M., Tutte, W.T.: A criterion for planarity of the square of a graph. J. Comb. Theory 2, 395---405 (1967)
[27]
He, X., Kao, M.-Y., Lu, H.-I.: A fast general methodology for information-theoretically optimal encodings of graphs. SIAM J. Comput. 30(3), 838---846 (2000)
[28]
Hell, P., Yu, X., Zhou, H.S.: Independence ratios of graph powers. Discrete Math. 127(1---3), 213---220 (1994)
[29]
Ho, C.-W., Lee, R.C.T.: Counting clique trees and computing perfect elimination schemes in parallel. Inf. Process. Lett. 31, 61---68 (1989)
[30]
Hsu, W.-L., Ma, T.-H.: Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Comput. 28, 1004---1020 (1999)
[31]
Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 549---554 (1989)
[32]
Kearney, P.E., Corneil, D.G.: Tree powers. J. Algorithms 29, 111---131 (1998)
[33]
Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms 2(2), 178---208 (2006)
[34]
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Comput. 18(1), 83---102 (2004)
[35]
Lin, Y.L., Skiena, S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8, 99---118 (1995)
[36]
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21, 193---201 (1992)
[37]
Markenzon, L., da Costa Pereira, P.R.: A compact representation for chordal graphs. In: Seventh Cologne Twente Workshop on Graphs and Combinatorial Optimization, pp. 174---176 (2008)
[38]
Mohar, B., Vodopivec, A.: The genus of Petersen powers. J. Graph Theory 67(1), 1---8 (2011)
[39]
Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph. J. Comb. Theory, Ser. B 94(2), 189---213 (2005)
[40]
Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54, 81---88 (1994)
[41]
Mukhopadhyay, A.: The square root of a graph. J. Comb. Theory 2, 290---295 (1967)
[42]
Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. SIAM J. Comput. 31(3), 762---776 (2001)
[43]
Nishimura, N., Ragde, P., Thilikos, D.M.: On graph powers for leaf-labeled trees. J. Algorithms 42(1), 69---108 (2002)
[44]
Rose, D., Tarjan, R., Lueker, G.: Algorithmic aspects of vertex elimination of graph. SIAM J. Comput. 5(2), 266---283 (1976)
[45]
Ross, I.C., Harary, F.: The squares of a tree. Bell Syst. Tech. J. 39, 641---647 (1960)
[46]
Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 134---149 (2010)
[47]
Simonyi, G.: Asymptotic values of the Hall-ratio for graph powers. Discrete Math. 306(19---20), 2593---2601 (2006)
[48]
Sreenivasa Kumar, P., Veni Madhavan, C.E.: Minimal vertex separators of chordal graphs. Discrete Appl. Math. 89, 155---168 (1998)
[49]
Sreenivasa Kumar, P., Veni Madhavan, C.E.: Clique tree generalization and new subclasses of chordal graphs. Discrete Appl. Math. 117, 109---131 (2002)
[50]
Tarjan, R., Yannakakis, M.: Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566---576 (1984)
[51]
van den Heuvel, J., McGuinness, S.: Coloring the square of a planar graph. J. Graph Theory 42(2), 110---124 (2003)
- Linear-Time Algorithms for Tree Root Problems
Recommendations
The 3-Steiner root problem
WG'07: Proceedings of the 33rd international conference on Graph-theoretic concepts in computer scienceFor a graph G and a positive integer k, the k-power of G is the graph Gk with V(G) as its vertex set and {(u,v)|u, v ∈ V(G), dG (u, v) ≤ k} as its edge set where dG(u, v) is the distance between u and v in graph G. The k-Steiner root problem on a graph ...
Computing bounded-degree phylogenetic roots of disconnected graphs
The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) (u,v)@_...
On Graph Powers for Leaf-Labeled Trees
We extend the well-studied concept of a graph power to that of a k-leaf powerG 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer Science+Business Media New York.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 February 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View all- Eppstein DHavvaei E(2020)Parameterized Leaf Power Recognition via Embedding into Graph ProductsAlgorithmica10.1007/s00453-020-00720-882:8(2337-2359)Online publication date: 29-May-2020