An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
From MaRDI portal
Publication:2408197
DOI10.1007/s00453-016-0230-zzbMath1372.68131OpenAlexW2914383530MaRDI QIDQ2408197
O-joung Kwon, Christophe Paul, Mamadou Moustapha Kanté, Eun Jung Kim
Publication date: 10 October 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5578/
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, 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
- Outerplanar obstructions for matroid pathwidth
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- Unit interval editing is fixed-parameter tractable
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Graph minors. XX: Wagner's conjecture
- Excluded vertex-minors for graphs of linear rank-width at most \(k\)
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- The structure of 3-connected matroids of path width three
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Graph operations characterizing rank-width
- Distance-hereditary graphs
- Which problems have strongly exponential complexity?
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- On the existence of subexponential parameterized algorithms
- The complexity of first-order and monadic second-order logic revisited
- Proper interval vertex deletion
- Linear time solvable optimization problems on graphs of bounded clique-width
- Obstructions for linear rank-width at most 1
- On Rota's conjecture and excluded minors containing large projective geometries.
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
- A Quartic Kernel for Pathwidth-One Vertex Deletion
- Measuring Indifference: Unit Interval Vertex Deletion
- Matroid Pathwidth and Code Trellis Complexity
- Decomposition of Directed Graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Constructive algorithm for path-width of matroids
- A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion.
- Interval Deletion Is Fixed-Parameter Tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Graph-Theoretic Concepts in Computer Science
