On the \(k\)-edge-incident subgraph problem and its variants

DOI10.1016/j.dam.2013.06.014zbMath1287.05092OpenAlexW1996888906MaRDI QIDQ2446891

Hongyu Liang

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

zbMATH Keywords

approximation algorithmpolynomial-time approximation schemedense graph\(k\)-edge-incident subgraph problemminimum partial vertex cover problem

Mathematics Subject Classification ID

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

On set expansion problems and the small set expansion conjecture

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