Approximating Bounded Degree Deletion via Matroid Matching
From MaRDI portal
Publication:5283370
DOI10.1007/978-3-319-57586-5_20zbMath1486.68130OpenAlexW2606695133MaRDI QIDQ5283370
Publication date: 21 July 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_20
Related Items
Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Approximating power node-deletion problems, Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, Kernels for packing and covering problems, Approximating Partially Bounded Degree Deletion on Directed Graphs
Cites Work
- Unnamed Item
- On a generalization of Nemhauser and Trotter's local optimization theorem
- On the weighted \(k\)-path vertex cover problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- On bounded-degree vertex deletion parameterized by treewidth
- On the hardness of approximating minimum vertex cover
- A new approach for approximating node deletion problems
- The node-deletion problem for hereditary properties is NP-complete
- Matroid matching and some applications
- A unified approximation algorithm for node-deletion problems
- On the \(k\)-path vertex cover of some graph products
- An analysis of the greedy algorithm for the submodular set covering problem
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- On approximation of the submodular set cover problem
- Minimum \(k\)-path vertex cover
- The complexity of dissociation set problems in graphs
- Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- The vertex cover \(P_3\) problem in cubic graphs
- On the vertex \(k\)-path cover
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Matroid Matching: The Power of Local Search
- Every Property of Hyperfinite Graphs Is Testable
- A better approximation ratio for the vertex cover problem
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A Linear Kernel for Co-Path/Cycle Packing
- Node-Deletion Problems on Bipartite Graphs
- Random pseudo-polynomial algorithms for exact matroid problems
- A graph‐theoretic generalization of the clique concept
- Approximating Node-Deletion Problems for Matroidal Properties
- Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
