Approximating bounded degree deletion via matroid matching
From MaRDI portal
Publication:5283370
DOI10.1007/978-3-319-57586-5_20zbMATH Open1486.68130OpenAlexW2606695133MaRDI QIDQ5283370FDOQ5283370
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
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
- The node-deletion problem for hereditary properties is NP-complete
- 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
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Minimum \(k\)-path vertex cover
- 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 \)
- A Linear Kernel for Co-Path/Cycle Packing
- 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 the hardness of approximating minimum vertex cover
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A better approximation ratio for the vertex cover problem
- Node-Deletion Problems on Bipartite Graphs
- Title not available (Why is that?)
- A graph‐theoretic generalization of the clique concept
- On bounded-degree vertex deletion parameterized by treewidth
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Matroid matching and some applications
- On a generalization of Nemhauser and Trotter's local optimization theorem
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Random pseudo-polynomial algorithms for exact matroid problems
- On approximation of the submodular set cover problem
- A new approach for approximating node deletion problems
- 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
- Matroid matching: the power of local search
- Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
- Every property of hyperfinite graphs is testable
- Approximating Node-Deletion Problems for Matroidal Properties
Cited In (8)
- Approximating Partially Bounded Degree Deletion on Directed Graphs
- Approximating power node-deletion problems
- Approximating power node-deletion problems
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- 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
- Kernels for packing and covering problems
- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
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)
