\(k\)-edge subgraph problems

DOI10.1016/S0166-218X(96)00030-3zbMath0870.68111MaRDI QIDQ1356515

Dorit S. Hochbaum, Olivier Goldschmidt

Publication date: 7 September 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

\(k\)-edge-incident subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The densest \(k\)-subgraph problem on clique graphs, The \textsc{max quasi-independent set} problem, On the \(k\)-edge-incident subgraph problem and its variants, On set expansion problems and the small set expansion conjecture, An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane, A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, On solving the densestk-subgraph problem on large graphs, The \(k\)-separator problem: polyhedra, complexity and approximation results, Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

Cites Work

• Some simplified NP-complete graph problems
• An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane
• Node-and edge-deletion NP-complete problems
• The dense \(k\)-subgraph problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item