Publication:5111250 - MaRDI portal

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 ² 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