Publication:5111250
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
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68Q27: Parameterized complexity, tractability and kernelization
Related Items
Unnamed Item, On the Complexity of Singly Connected Vertex Deletion, Adapting the Directed Grid Theorem into an FPT Algorithm, On the complexity of singly connected vertex deletion, Towards a polynomial kernel for directed feedback vertex set
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