scientific article; zbMATH DE number 7204370
From MaRDI portal
DOI10.4230/LIPIcs.MFCS.2017.36zbMath1441.68163MaRDI QIDQ5111250
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, M. S. Ramanujan, Sebastian Ordyniak
Publication date: 26 May 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
On the Complexity of Singly Connected Vertex Deletion, Towards a polynomial kernel for directed feedback vertex set, Adapting the Directed Grid Theorem into an FPT Algorithm, Unnamed Item, On the complexity of singly connected vertex deletion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Disjoint cycles intersecting a set of vertices
- Improved algorithms for feedback vertex set problems
- A cubic kernel for feedback vertex set and loop cutset
- Packing directed circuits
- Approximating minimum feedback sets and multicuts in directed graphs
- Packing directed circuits fractionally
- Packing circuits in eulerian digraphs
- Faster deterministic \textsc{Feedback Vertex Set}
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Packing cycles through prescribed vertices
- On the hardness of losing width
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- A 4 k 2 kernel for feedback vertex set
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- (Meta) Kernelization
- On Feedback Vertex Set New Measure and New Structures
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Reducibility among Combinatorial Problems
- On Independent Circuits Contained in a Graph
- Inapproximability of H-Transversal/Packing
- Half-integrality, LP-branching and FPT Algorithms
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Packing directed cycles through a specified vertex set
