Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
type: Item
instance of: scholarly article
title: Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
zbMATH Open document ID: 1397.68106
author: Diptapriyo Majumdar
author: Venkatesh Raman
published in: Algorithmica
publication date: 2018-07-26T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6911204
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: feedback vertex set
zbMATH Keywords: structural parameterization
zbMATH Keywords: W-hardness
MaRDI profile type: Publication
full work available at URL: s00453-018-0419-4
OpenAlex ID: W2789598654
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: A cubic kernel for feedback vertex set and loop cutset
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
cites work: A fast branching algorithm for cluster vertex deletion
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: \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
cites work: Parameterized Algorithms
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Graph Theory
cites work: Fundamentals of parameterized complexity
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: Parametrized complexity theory.
cites work: Vertex cover problem parameterized above and below tight bounds
cites work: Vertex Cover Structural Parameterization Revisited
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: A unified approximation algorithm for node-deletion problems
cites work: Q4198056
cites work: Which problems have strongly exponential complexity?
cites work: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
cites work: Data reduction for graph coloring problems
cites work: Faster deterministic \textsc{Feedback Vertex Set}
cites work: Q5275384
cites work: Feedback vertex set on AT-free graphs
cites work: Q5363786
cites work: Minimum weakly fundamental cycle bases are hard to find
cites work: A 4 k 2 kernel for feedback vertex set
cites work: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
DOI: 10.1007/S00453-018-0419-4
description: scientific article; zbMATH DE number 6911204