A cubic kernel for feedback vertex set and loop cutset
From MaRDI portal
Publication:968273
DOI10.1007/S00224-009-9234-2zbMATH Open1215.68170OpenAlexW2043644213WikidataQ59567646 ScholiaQ59567646MaRDI QIDQ968273FDOQ968273
Hans L. Bodlaender, Thomas C. van Dijk
Publication date: 5 May 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9234-2
Recommendations
algorithmsgraphsdata reductionfeedback vertex setfixed parameter tractabilitypreprocessingkernelization algorithmspolynomial kernelsloop cutset
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Title not available (Why is that?)
- ON DISJOINT CYCLES
- Title not available (Why is that?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Vertex packings: Structural properties and algorithms
- Computing and Combinatorics
- Title not available (Why is that?)
- A Short Proof of the Factor Theorem for Finite Graphs
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- A Linear Kernel for Planar Feedback Vertex Set
- Polynomial-time data reduction for dominating set
- Title not available (Why is that?)
- Vertex cover: Further observations and further improvements
- A More Effective Linear Kernelization for Cluster Editing
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Necessary edges in \(k\)-chordalisations of graphs
- Maximum skew-symmetric flows and matchings
- Exact Computation of Maximum Induced Forest
- On Problems without Polynomial Kernels (Extended Abstract)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
- Title not available (Why is that?)
- Algorithms and Data Structures
Cited In (26)
- Parameterized complexity of vertex deletion into perfect graph classes
- Kernelization: new upper and lower bound techniques
- Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
- Towards a polynomial kernel for directed feedback vertex set
- Title not available (Why is that?)
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Kernelization for feedback vertex set via elimination distance to a forest
- A Cubic Kernel for Feedback Vertex Set
- Kernelization for feedback vertex set via elimination distance to a forest
- Title not available (Why is that?)
- Polynomial kernels for deletion to classes of acyclic digraphs
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Search-space reduction via essential vertices
- A \(13k\)-kernel for planar feedback vertex set via region decomposition
- Kernel bounds for disjoint cycles and disjoint paths
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Title not available (Why is that?)
- A Quartic Kernel for Pathwidth-One Vertex Deletion
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- Approximation and Kernelization for Chordal Vertex Deletion
- Faster deterministic \textsc{Feedback Vertex Set}
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
Uses Software
This page was built for publication: A cubic kernel for feedback vertex set and loop cutset
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968273)
