Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
DOI10.1007/S00453-022-00984-2OpenAlexW3217285817MaRDI QIDQ2093579FDOQ2093579
Authors: Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk 
Publication date: 27 October 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.01868
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68Wxx) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05Cxx)
Cites Work
- Fundamentals of parameterized complexity
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The node-deletion problem for hereditary properties is NP-complete
- Characterizations of outerplanar graphs
- A partial k-arboretum of graphs with bounded treewidth
- Heuristics for the maximum outerplanar subgraph problem
- Title not available (Why is that?)
- Parameterized algorithms
- Graph minors. V. Excluding a planar graph
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Title not available (Why is that?)
- Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
- Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
- Lower and upper bounds for long induced paths in 3-connected planar graphs
- Excluded-minor characterization of apex-outerplanar graphs
- Hitting forbidden minors: approximation and kernelization
- Minor‐order obstructions for the graphs of vertex cover 6
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- Vertex cover: Further observations and further improvements
- On computing graph minor obstruction sets
- Outerplanar obstructions for a feedback vertex set
- Title not available (Why is that?)
- Forbidden minors to graphs with small feedback sets
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Minimal cycle bases of outerplanar graphs
- Title not available (Why is that?)
- Upper bounds on the size of obstructions and intertwines
- (Meta) kernelization
- Approximation and kernelization for chordal vertex deletion
- Kernelization. Theory of parameterized preprocessing
- Pathwidth of outerplanar graphs
- Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
- A quartic kernel for pathwidth-one vertex deletion
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Partitioning a graph into small pieces with applications to path transversal
- Crossing-optimal acyclic HP-completion for outerplanar \(st\)-digraphs
- Losing Treewidth by Separating Subsets
- Relaxations of graph isomorphism
Cited In (3)
Uses Software
This page was built for publication: Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093579)
