Approximating bounded degree deletion via matroid matching

Recommendations

Approximating partially bounded degree deletion on directed graphs
Approximating partially bounded degree deletion on directed graphs
Degree Bounded Matroids and Submodular Flows
On structural parameterizations of the bounded-degree vertex deletion problem
On structural parameterizations of the bounded-degree vertex deletion problem

Cites work

scientific article; zbMATH DE number 3544074 (Why is no real title available?)
A better approximation ratio for the vertex cover problem
A factor 2 approximation algorithm for the vertex cover P₃ problem
A fixed-parameter algorithm for the vertex cover \(P_3\) 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 new approach for approximating node deletion problems
A primal-dual approximation algorithm for the vertex cover P^3 problem
A unified approximation algorithm for node-deletion problems
An analysis of the greedy algorithm for the submodular set covering problem
Approximating Node-Deletion Problems for Matroidal Properties
Clique relaxations in social network analysis: the maximum \(k\)-plex problem
Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
Every property of hyperfinite graphs is testable
Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
Matroid matching and some applications
Matroid matching: the power of local search
Minimum \(k\)-path vertex cover
Node-Deletion Problems on Bipartite Graphs
On approximation of the submodular set cover problem
On bounded-degree vertex deletion parameterized by treewidth
On computing the minimum 3-path vertex cover and dissociation number of graphs
On the k-path vertex cover of some graph products
On the hardness of approximating minimum vertex cover
On the vertex \(k\)-path cover
On the weighted \(k\)-path vertex cover problem
Random pseudo-polynomial algorithms for exact matroid problems
Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
The complexity of dissociation set problems in graphs
The node-deletion problem for hereditary properties is NP-complete
The vertex cover \(P_3\) problem in cubic graphs
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(13)

Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
Approximating power node-deletion problems
Approximating power node-deletion problems
Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
Approximating partially bounded degree deletion on directed graphs
On structural parameterizations of the bounded-degree vertex deletion problem
Approximating partially bounded degree deletion on directed graphs
On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
Degree bounded matroids and submodular flows
Kernels for packing and covering problems
On structural parameterizations of the bounded-degree vertex deletion problem

This page was built for publication: Approximating bounded degree deletion via matroid matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283370)