A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
From MaRDI portal
Publication:1672007
DOI10.1016/j.jcss.2018.05.005zbMath1402.68199arXiv1604.06056OpenAlexW2963729476WikidataQ115571246 ScholiaQ115571246MaRDI QIDQ1672007
O-joung Kwon, Eduard Eiben, Robert Ganian
Publication date: 7 September 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.06056
Analysis of algorithms (68W40) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Graph reconstruction in the congested clique ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
Cites Work
- Fundamentals of parameterized complexity
- Parameterized complexity of vertex deletion into perfect graph classes
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- The behavior of clique-width under graph operations and graph transformations
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Finding odd cycle transversals.
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Fixed-parameter algorithms for cluster vertex deletion
- Graph minors. V. Excluding a planar graph
- Distance-hereditary graphs
- On the extension of bipartite to parity graphs
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Linear time solvable optimization problems on graphs of bounded clique-width
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- A polynomial kernel for block graph deletion
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- The Hamiltonian problem on distance-hereditary graphs
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Computing maximum stable sets for distance-hereditary graphs
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- Kernelization Using Structural Parameters on Sparse Graph Classes
- Solving Problems on Graphs of High Rank-Width
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- Graph Layout Problems Parameterized by Vertex Cover
- Transforming trees by successive local complementations
- A Combinatorial Decomposition Theory
- Decomposition of Directed Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Recognizing circle graphs in polynomial time
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Meta-kernelization using Well-structured Modulators
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Parameterized Algorithms
- A polynomial kernel for distance-hereditary vertex deletion
This page was built for publication: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
