Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
type: Item
instance of: scholarly article
title: Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
author: Huib Donkers
author: Bart M. P. Jansen
author: Michał Włodarczyk
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2110.01868
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7608295
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: kernelization
zbMATH Keywords: outerplanar graphs
describes a project that uses: Algorithm 447
MaRDI profile type: Publication
OpenAlex ID: W3217285817
cites work: Kernelization
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Hitting forbidden minors: approximation and kernelization
cites work: Uniform Kernelization Complexity of Hitting Forbidden Minors
cites work: Polynomial kernels for hitting forbidden minors under structural parameterizations
cites work: Hitting and Harvesting Pumpkins
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Graph minors. V. Excluding a planar graph
cites work: Vertex cover: Further observations and further improvements
cites work: Relaxations of graph isomorphism
cites work: A 4 k 2 kernel for feedback vertex set
cites work: A Quartic Kernel for Pathwidth-One Vertex Deletion
cites work: An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
cites work: Q5545841
cites work: Pathwidth of outerplanar graphs
cites work: Excluded-minor characterization of apex-outerplanar graphs
cites work: Q4121921
cites work: Characterizations of outerplanar graphs
cites work: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
cites work: Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
cites work: Crossing-optimal acyclic HP-completion for outerplanar \(st\)-digraphs
cites work: Lower and upper bounds for long induced paths in 3-connected planar graphs
cites work: Minimal cycle bases of outerplanar graphs
cites work: Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
cites work: Heuristics for the maximum outerplanar subgraph problem
cites work: On computing graph minor obstruction sets
cites work: Q4520532
cites work: Forbidden minors to graphs with small feedback sets
cites work: Minor‐order obstructions for the graphs of vertex cover 6
cites work: Upper bounds on the size of obstructions and intertwines
cites work: Outerplanar obstructions for a feedback vertex set
cites work: (Meta) Kernelization
cites work: Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Losing Treewidth by Separating Subsets
cites work: Partitioning a graph into small pieces with applications to path transversal
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
DOI: 10.1007/S00453-022-00984-2
description: scientific article; zbMATH DE number 7608295