Parameterised algorithms for deletion to classes of DAGs
From MaRDI portal
Publication:2322699
DOI10.1007/s00224-018-9852-7zbMath1430.68170OpenAlexW2794218108MaRDI QIDQ2322699
Akanksha Agrawal, Saket Saurabh, Meirav Zehavi, Roohani Sharma
Publication date: 5 September 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-018-9852-7
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- 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 kernelization algorithm for \(d\)-hitting set
- 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
- Fixed-parameter tractability results for feedback set problems in tournaments
- Packing cycles through prescribed vertices
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- An FPT algorithm for Tree Deletion Set
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- A fixed-parameter algorithm for the directed feedback vertex set problem
- 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
- Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Exact Algorithms via Monotone Local Search
- 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
This page was built for publication: Parameterised algorithms for deletion to classes of DAGs