Computing optimal leaf roots of chordal cographs in linear time

DOI10.7155/JGAA.V28I1.2942MaRDI QIDQ6616231zbMATH OpenFDO

Authors Van Bang Le, Christian Rosenke

Publication date 8 October 2024

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

\(k\)-leaf power\(k\)-leaf rootchordal cographoptimal \(k\)-leaf roottrivially perfect leaf power

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Recommendations

• Rooted directed path graphs are leaf powers
• Strictly chordal graphs are leaf powers
• On (k,ℓ)-Leaf Powers
• Characterising \((k,\ell )\)-leaf powers
• Structure and linear time recognition of 3-leaf powers

Cites work

• A Note on "The Comparability Graph of a Tree"
• Complement reducible graphs
• Computing Optimal Leaf Roots of Chordal Cographs in Linear Time
• Leaf powers
• Linear-time recognition of circular-arc graphs
• On graph powers for leaf-labeled trees
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Recognizing \(k\)-leaf powers in polynomial time, for constant \(k\)
• Rooted directed path graphs are leaf powers
• Structure and linear time recognition of 3-leaf powers
• Structure and linear-time recognition of 4-leaf powers
• The 3-Steiner Root Problem
• The 4-Steiner Root problem
• The Comparability Graph of a Tree
• The complete inclusion structure of leaf power classes
• Trivially perfect graphs

This page was built for publication: Computing optimal leaf roots of chordal cographs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6616231)