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
(41)- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Approximation algorithms for minimum (weight) connected k-path vertex cover
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Conflict free version of covering problems on graphs: classical and parameterized
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
- Approximation algorithm for minimum connected 3-path vertex cover
- Approximation algorithms for minimum weight connected 3-path vertex cover
- Node-and edge-deletion NP-complete problems
- Structural parameterizations for two bounded degree problems revisited
- Combination of parallel machine scheduling and vertex cover
- Approximating power node-deletion problems
- Approximating power node-deletion problems
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- Rank reduction of oriented graphs by vertex and edge deletions
- Approximating bounded degree deletion via matroid matching
- The weighted k-path vertex cover problem on series-parallel graphs
- scientific article; zbMATH DE number 7525474 (Why is no real title available?)
- Approximating partially bounded degree deletion on directed graphs
- A unified local ratio approximation of node-deletion problems
- Quadratic vertex kernel for split vertex deletion
- Vertex cover structural parameterization revisited
- Approximation algorithm for the minimum weight connected k-subgraph cover problem
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Approximating Node-Deletion Problems for Matroidal Properties
- Graph orientation with splits
- Faster parameterized algorithms for deletion to split graphs
- Polynomial Kernel for Interval Vertex Deletion
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Algorithm for online 3-path vertex cover
- A new approach for approximating node deletion problems
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Kernels for packing and covering problems
- A polynomial kernel for bipartite permutation vertex deletion
- Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem
- Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization
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)
