Polynomial kernels for deletion to classes of acyclic digraphs
From MaRDI portal
Publication:1751231
DOI10.1016/j.disopt.2017.02.002zbMath1387.68137OpenAlexW2593070308MaRDI QIDQ1751231
Matthias Mnich, Erik Jan van Leeuwen
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5756/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)
Related Items (9)
On the Complexity of Singly Connected Vertex Deletion ⋮ Faster algorithm for pathwidth one vertex deletion ⋮ A polynomial kernel for funnel arc deletion set ⋮ Faster parameterized algorithm for pumpkin vertex deletion set ⋮ Unnamed Item ⋮ A Polynomial Kernel for Funnel Arc Deletion Set. ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ On the complexity of singly connected vertex deletion ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- A cubic kernel for feedback vertex set and loop cutset
- A kernelization algorithm for \(d\)-hitting set
- The node-deletion problem for hereditary properties is NP-complete
- Approximating minimum feedback sets and multicuts in directed graphs
- Face covers and the genus problem for apex graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Packing directed circuits fractionally
- 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
- Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)
- A fixed-parameter algorithm for the directed feedback vertex set problem
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Reducibility among Combinatorial Problems
- On the completeness of a generalized matching problem
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Parameterized Algorithms
This page was built for publication: Polynomial kernels for deletion to classes of acyclic digraphs
