Approximating partially bounded degree deletion on directed graphs
From MaRDI portal
(Redirected from Publication:5240368)
Approximating partially bounded degree deletion on directed graphs (scientific article; zbMATH DE number 7122266)
Approximating partially bounded degree deletion on directed graphs (scientific article; zbMATH DE number 7122266)
Vertex degrees (05C07) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Recommendations
- Approximating partially bounded degree deletion on directed graphs
- Approximating bounded degree deletion via matroid matching
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the bounded-degree vertex deletion problem
Cites work
- 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₃ 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 New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- 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 bounded degree deletion via matroid matching
- Approximating partially bounded degree deletion on directed graphs
- Approximation algorithms for partial covering problems
- Clique relaxations in social network analysis: the maximum k-plex problem
- Covering analysis of the greedy algorithm for partial cover
- Every property of hyperfinite graphs is testable
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- scientific article; zbMATH DE number 1947055 (Why is no real title available?)
- Improved performance of the greedy algorithm for partial cover
- 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
- Partial domination in graphs
- Partial vs. Complete Domination: t-Dominating Set
- Partitioning a graph into small pieces with applications to path transversal
- Randomized parameterized algorithms for P₂-packing and co-path packing problems
- The complexity of dissociation set problems in graphs
- The vertex cover \(P_3\) problem in cubic graphs
- Using homogeneous weights for approximating the partial cover problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(7)- Approximating partially bounded degree deletion on directed graphs
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- A unified local ratio approximation of node-deletion problems
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- Approximating bounded degree deletion via matroid matching
- Approximating power node-deletion problems
This page was built for publication: Approximating partially bounded degree deletion on directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5240368)
