Parameterized leaf power recognition via embedding into graph products

DOI10.4230/LIPICS.IPEC.2018.16MaRDI QIDQ5009478zbMATH OpenOpenAlexFDO

Authors David Eppstein, Elham Havvaei

Publication date 4 August 2021

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

zbMATH Keywords

phylogenetic treefixed-parameter tractabilitymonadic second-order logicstrong product of graphsCourcelle's theoremleaf power

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Recommendations

• Parameterized leaf power recognition via embedding into graph products
• Structure and linear time recognition of 3-leaf powers
• On (k,ℓ)-Leaf Powers
• Leaf Powers and Their Properties: Using the Trees
• Rooted directed path graphs are leaf powers

Cites work

• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1059243 (Why is no real title available?)
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• Algorithms and Computation
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Computing crossing numbers in quadratic time
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Handle-rewriting hypergraph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Nonserial dynamic programming
• On graph powers for leaf-labeled trees
• On k- Versus (k + 1)-Leaf Powers
• Parameterized leaf power recognition via embedding into graph products
• Practical access to dynamic programming on tree decompositions
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Rooted directed path graphs are leaf powers
• S-functions for graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Some remarks about leaf roots
• Strictly chordal 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 Clique-Width of Tree-Power and Leaf-Power Graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(1)

• Parameterized leaf power recognition via embedding into graph products

This page was built for publication: Parameterized leaf power recognition via embedding into graph products

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