Parameterized leaf power recognition via embedding into graph products

DOI10.1007/s00453-020-00720-8zbMath1452.68135OpenAlexW2950378209MaRDI QIDQ786044

Elham Havvaei, David Eppstein

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10217/

zbMATH Keywords

dynamic programmingmonadic second-order logictree decompositionphylogenetic treestrong product of graphsfixed-parameter tractableCourcelle's theoremleaf power

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ Unnamed Item ⋮ On the treewidth of Hanoi graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure and linear time recognition of 3-leaf powers
• Strictly chordal graphs are leaf powers
• The square of a block graph
• Rooted directed path graphs are leaf powers
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• S-functions for graphs
• Treewidth. Computations and approximations
• On the planar split thickness of graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• The 4-Steiner Root problem
• Linear-time algorithms for tree root problems
• Handle-rewriting hypergraph grammars
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Some remarks about leaf roots
• Contribution to nonserial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On Graph Powers for Leaf-Labeled Trees
• Finding Cactus Roots in Polynomial Time
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Bipartite roots of graphs
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Easy problems for tree-decomposable graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• Graph minors. II. Algorithmic aspects of tree-width
• Smallest-last ordering and clustering and graph coloring algorithms
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Structure and linear-time recognition of 4-leaf powers
• Practical Access to Dynamic Programming on Tree Decompositions
• Computing crossing numbers in quadratic time
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On k- Versus (k + 1)-Leaf Powers
• k-Degenerate Graphs
• Algorithms and Computation
• Hardness Results and Efficient Algorithms for Graph Powers
• Graph-Theoretic Concepts in Computer Science
• Finding cut-vertices in the square roots of a graph

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