Recognizing k -Leaf Powers in Polynomial Time, for Constant k

DOI10.1145/3614094arXiv2110.15421OpenAlexW3210535977MaRDI QIDQ6075860

Manuel Lafond

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2110.15421

zbMATH Keywords

algorithmsgraph theoryleaf powers

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Towards a characterization of leaf powers by clique arrangements
• Parameterized leaf power recognition via embedding into graph products
• Structure and linear time recognition of 3-leaf powers
• Strictly chordal graphs are leaf powers
• Rooted directed path graphs are leaf powers
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• On strongly chordal graphs that are not leaf powers
• The 4-Steiner Root problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Some remarks about leaf roots
• On Graph Powers for Leaf-Labeled Trees
• Pairwise Compatibility Graphs: A Survey
• Statistical Inference of Phylogenies
• The 3-Steiner Root Problem
• On (k,ℓ)-Leaf Powers
• Kernelization: New Upper and Lower Bound Techniques
• Kernelization
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Structure and linear-time recognition of 4-leaf powers
• A survey on pairwise compatibility graphs
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On k- Versus (k + 1)-Leaf Powers
• Algorithms and Computation
• Linear-Time Algorithms for Tree Root Problems
• Graph-Theoretic Concepts in Computer Science
• Recognition of linear and star variants of leaf powers is in P
• On the domination number of $t$-constrained de Bruijn graphs

This page was built for publication: Recognizing k -Leaf Powers in Polynomial Time, for Constant k