Approximating power node-deletion problems
From MaRDI portal
Recommendations
- A new approach for approximating node deletion problems
- A unified approximation algorithm for node-deletion problems
- Approximating Node-Deletion Problems for Matroidal Properties
- Node-and edge-deletion NP-complete problems
- A unified local ratio approximation of node-deletion problems
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Approximating partially bounded degree deletion on directed graphs
- Approximating partially bounded degree deletion on directed graphs
- On the complexity of bounded deletion propagation
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A better approximation ratio for the vertex cover problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- A graph‐theoretic generalization of the clique concept
- A linear kernel for co-path/cycle packing
- A naive algorithm for feedback vertex set
- A new approach for approximating node deletion problems
- A unified approximation algorithm for node-deletion problems
- A unified local ratio approximation of node-deletion problems
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximating Clique and Biclique Problems
- Approximating bounded degree deletion via matroid matching
- Clique relaxations in social network analysis: the maximum k-plex problem
- Covering Problems with Hard Capacities
- Every property of hyperfinite graphs is testable
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Min-Power Covering Problems
- On approximation of the submodular set cover problem
- On bounded-degree vertex deletion parameterized by treewidth
- On independent sets, 2-to-2 games, and Grassmann graphs
- On the power of unique 2-prover 1-round games
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Randomized parameterized algorithms for P₂-packing and co-path packing problems
- Reducibility among combinatorial problems
- The Rectilinear Steiner Tree Problem is NP-Complete
- The minimum generalized vertex cover problem
- The node-deletion problem for hereditary properties is NP-complete
- Towards a proof of the 2-to-1 games conjecture?
- Using homogeneous weights for approximating the partial cover problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(2)
This page was built for publication: Approximating power node-deletion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057334)
