On the \(k\)-edge-incident subgraph problem and its variants
From MaRDI portal
Publication:2446891
DOI10.1016/j.dam.2013.06.014zbMath1287.05092OpenAlexW1996888906MaRDI QIDQ2446891
Publication date: 23 April 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.06.014
approximation algorithmpolynomial-time approximation schemedense graph\(k\)-edge-incident subgraph problemminimum partial vertex cover problem
Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- Improved approximation bounds for edge dominating set in dense graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- \(k\)-edge subgraph problems
- The densest \(k\)-subgraph problem on clique graphs
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- Detecting high log-densities
- Dial a Ride from k -forest
- The Design of Approximation Algorithms
- Densest k-Subgraph Approximation on Intersection Graphs
- A threshold of ln n for approximating set cover
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- PTAS for Densest k-Subgraph in Interval Graphs