A unified approximation algorithm for node-deletion problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1003266 (Why is no real title available?)
- scientific article; zbMATH DE number 3889282 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Node-Deletion NP-Complete Problems
- On the Fractional Solution to the Set Covering Problem
- Optimization, approximation, and complexity classes
- Packing directed circuits fractionally
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Some simplified NP-complete graph problems
- The approximation of maximum subgraph problems
- The node-deletion problem for hereditary properties is NP-complete
Cited in
(39)- A polynomial kernel for bipartite permutation vertex deletion
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Vertex cover structural parameterization revisited
- Approximating bounded degree deletion via matroid matching
- Combination of parallel machine scheduling and vertex cover
- Faster parameterized algorithms for deletion to split graphs
- Approximating power node-deletion problems
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Node-and edge-deletion NP-complete problems
- Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem
- A unified local ratio approximation of node-deletion problems
- Kernels for packing and covering problems
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- Quadratic vertex kernel for split vertex deletion
- Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization
- Rank reduction of oriented graphs by vertex and edge deletions
- Conflict free version of covering problems on graphs: classical and parameterized
- A new approach for approximating node deletion problems
- The weighted \(k\)-path vertex cover problem on series-parallel graphs
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- Approximation algorithm for minimum connected 3-path vertex cover
- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
- scientific article; zbMATH DE number 7525474 (Why is no real title available?)
- Algorithm for online 3-path vertex cover
- Approximation algorithms for minimum weight connected 3-path vertex cover
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Approximating power node-deletion problems
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- Graph orientation with splits
- Polynomial Kernel for Interval Vertex Deletion
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Approximating partially bounded degree deletion on directed graphs
This page was built for publication: A unified approximation algorithm for node-deletion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1270821)
