Parameterized leaf power recognition via embedding into graph products
DOI10.1007/S00453-020-00720-8zbMATH Open1452.68135OpenAlexW2950378209MaRDI QIDQ786044FDOQ786044
Authors: David Eppstein, Elham Havvaei 
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/
Recommendations
phylogenetic treedynamic programmingmonadic second-order logicstrong product of graphstree decompositionfixed-parameter tractableCourcelle's theoremleaf power
Problems related to evolution (92D15) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph operations (line graphs, products, etc.) (05C76) Logic in computer science (03B70) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Bipartite roots of graphs
- Easy problems for tree-decomposable graphs
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Smallest-last ordering and clustering and graph coloring algorithms
- Title not available (Why is that?)
- k-Degenerate Graphs
- The square of a block graph
- Graph minors. II. Algorithmic aspects of tree-width
- Treewidth. Computations and approximations
- Computing crossing numbers in quadratic time
- S-functions for graphs
- Hardness Results and Efficient Algorithms for Graph Powers
- Branch-width, parse trees, and monadic second-order logic for matroids.
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Some remarks about leaf roots
- On graph powers for leaf-labeled trees
- The Clique-Width of Tree-Power and Leaf-Power Graphs
- The 3-Steiner Root Problem
- Structure and linear-time recognition of 4-leaf powers
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- On k- Versus (k + 1)-Leaf Powers
- Graph-Theoretic Concepts in Computer Science
- Structure and linear time recognition of 3-leaf powers
- Rooted directed path graphs are leaf powers
- Title not available (Why is that?)
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Listing all maximal cliques in sparse graphs in near-optimal time
- Strictly chordal graphs are leaf powers
- Algorithms and Computation
- Contribution to nonserial dynamic programming
- Finding cactus roots in polynomial time
- The 4-Steiner Root problem
- Linear-time algorithms for tree root problems
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Title not available (Why is that?)
- Practical access to dynamic programming on tree decompositions
- Finding cut-vertices in the square roots of a graph
Cited In (9)
- Title not available (Why is that?)
- 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
- Computing optimal leaf roots of chordal cographs in linear time
- Closest 4-leaf power is fixed-parameter tractable
- Parameterized leaf power recognition via embedding into graph products
- On the treewidth of Hanoi graphs
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 Q786044)
