Exact leaf powers

DOI10.1016/j.tcs.2010.04.027zbMath1193.05141OpenAlexW2014863096MaRDI QIDQ982668

Dieter Rautenbach, Andreas Brandstädt, Van Bang Le

Publication date: 7 July 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.027

zbMATH Keywords

phylogenyphylogenetic treeforbidden induced subgraphgraph powerleaf powerleaf root

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Pairwise Compatibility Graphs: A Survey ⋮ Exact-2-relation graphs ⋮ Inferring phylogenetic trees from the knowledge of rare evolutionary events ⋮ On graphs that are not PCGs ⋮ Simplicial Powers of Graphs ⋮ On k- Versus (k + 1)-Leaf Powers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tolerance graphs
• Structure and linear time recognition of 3-leaf powers
• Characterizations of strongly chordal graphs
• Modular decomposition and transitive orientation
• Computing roots of graphs is hard
• NeST graphs
• Neighborhood subtree tolerance graphs
• A characterisation of rigid circuit graphs
• Some remarks about leaf roots
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On Graph Powers for Leaf-Labeled Trees
• A Class of Balanced Matrices Arising from Location Problems
• Locality in Distributed Graph Algorithms
• Tree Powers
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• Four Characters Suffice to Convexly Define a Phylogenetic Tree
• Depth-First Search and Linear Graph Algorithms
• Algorithms and Computation