An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
type: Item
instance of: scholarly article
title: An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
zbMATH Open document ID: 1252.68150
author: Marek Cygan
author: Marcin Pilipczuk
author: Michał Pilipczuk
author: Jakub Onufry Wojtaszczyk
published in: Algorithmica
publication date: 2012-11-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6109462
zbMATH Keywords: fixed parameter tractability
zbMATH Keywords: kernelization
zbMATH Keywords: pathwidth
zbMATH Keywords: caterpillar graph
MaRDI profile type: Publication
full work available at URL: s00453-011-9578-2
OpenAlex ID: W2130067129
cites work: The Proper Interval Colored Graph problem for caterpillar trees
cites work: Q4281679
cites work: The Bandwidth of Caterpillars with Hairs of Length 1 and 2
cites work: On Feedback Vertex Set New Measure and New Structures
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: A fixed-parameter approach to 2-layer planarization
cites work: Parametrized complexity theory.
cites work: Graph bandwidth of weighted caterpillars
cites work: Matching theory
cites work: Algorithms – ESA 2004
cites work: Q5710169
cites work: Graphs and matching theorems
cites work: The NP-completeness of the bandwidth minimization problem
cites work: A Quartic Kernel for Pathwidth-One Vertex Deletion
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Two-Layer Planarization Parameterized by Feedback Edge Set
DOI: 10.1007/S00453-011-9578-2
description: scientific article; zbMATH DE number 6109462