Structure and linear-time recognition of 4-leaf powers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Structure and linear-time recognition of 4-leaf powers

Full text

Pdf (300 KB)

Source

ACM Transactions on Algorithms (TALG) archive
Volume 5 , Issue 1 (November 2008) table of contents

Article No. 11

Year of Publication: 2008

ISSN:1549-6325

Authors

Andreas Brandstädt	Universität Rostock, Rostock, Germany
Van Bang Le	Universität Rostock, Rostock, Germany
R. Sritharan	The University of Dayton, Dayton, OH

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 124, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1435375.1435386 What is a DOI?

ABSTRACT

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is a k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O(n³)-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andreas Brandstädt , Van Bang Le, Structure and linear time recognition of 3-leaf powers, Information Processing Letters, v.98 n.4, p.133-138, 31 May 2006 [doi>10.1016/j.ipl.2006.01.004]
	2	Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
	3	Chen, Z.-Z., Jiang, T., and Lin, G. 2003. Computing phylogenetic roots with bounded degrees and errors. SIAM J. Comput. 32, 864--879.
	4	Dahlhaus, E., and Duchet, P. 1987. On strongly chordal graphs. Ars Combin. 24 B, 23--30.
	5	Dom, M., Guo, J., Hüffner, F., and Niedermeier, R. 2005. Extending the tractability border for closest leaf powers. In Proceedings of the 31st Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 3787. Springer, 397--408.
	6	Harary, F. 1972. Graph Theory. Addison-Wesley, MA.
	7	B. Jamison , S. Olariu, A tree representation for P4-sparse graphs, Discrete Applied Mathematics, v.35 n.2, p.115-129, Jan. 9, 1992 [doi>10.1016/0166-218X(92)90036-A]
	8	Paul E. Kearney , Derek G. Corneil, Tree powers, Journal of Algorithms, v.29 n.1, p.111-131, Oct. 1998 [doi>10.1006/jagm.1998.9999]
	9	Lap Chi Lau, Bipartite roots of graphs, ACM Transactions on Algorithms (TALG), v.2 n.2, p.178-208, April 2006 [doi>10.1145/1150334.1150337]
	10	Guo-Hui Lin , Tao Jiang , Paul E. Kearney, Phylogenetic k-Root and Steiner k-Root, Proceedings of the 11th International Conference on Algorithms and Computation, p.539-551, December 18-20, 2000
	11	Yaw-Ling Lin , Steven S. Skiena, Algorithms for Square Roots of Graphs, SIAM Journal on Discrete Mathematics, v.8 n.1, p.99-118, Feb. 1995 [doi>10.1137/S089548019120016X]
	12	Lubiw, A. 1982. Γ-free matrices. M.S. thesis, University of Waterloo, Canada.
	13	Ross M. McConnell , Jeremy P. Spinrad, Modular decomposition and transitive orientation, Discrete Mathematics, v.201 n.1-3, p.189-241, April 28, 1999 [doi>10.1016/S0012-365X(98)00319-7]
	14	Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, On graph powers for leaf-labeled trees, Journal of Algorithms, v.42 n.1, p.69-108, January 2002 [doi>10.1006/jagm.2001.1195]
	15	Rautenbach, D. 2006. Some remarks about leaf roots. Discrete Math. 306, 1456--1461.
	16	Raychaudhuri, A. 1992. On powers of strongly chordal and circular arc graphs. Ars Combin. 34, 147--160.
	17	Rose, D. J., Tarjan, R. E., and Lueker, G. S. 1976. Algorithmic aspects of vertex elimination on graph. SIAM J. Comput. 5, 266--283.
	18	Ross, I. C., and Harary, F. 1960. The square of a tree. Bell Syst. Tech. J. 39, 641--647.
	19	Spinrad, J. P. 2003. Efficient Graph Representations. Fields Institute Monographs, Toronto.
	20	Tarjan, R. E. 1972. Depth first search and linear time algorithms. SIAM J. Comput. 1, 146--160.
	21	Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]