Computing optimal leaf roots of chordal cographs in linear time

DOI10.7155/jgaa.v28i1.2942zbMath1548.05315MaRDI QIDQ6616231

Christian Rosenke, Van Bang Le

Publication date: 8 October 2024

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Cites Work

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

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