On approximability of the independent/connected edge dominating set problems
From MaRDI portal
Publication:1603390
DOI10.1016/S0020-0190(01)00138-7zbMath1032.68120MaRDI QIDQ1603390
Publication date: 14 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
68R05: Combinatorics in computer science
68R10: Graph theory (including graph drawing) in computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- Approximating the tree and tour covers of a graph
- On approximating the minimum independent dominating set
- Depth-first search and the vertex cover problem
- Geometric algorithms and combinatorial optimization
- Parallel concepts in graph theory
- Approximation algorithms for connected dominating sets
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- An analysis of the greedy algorithm for the submodular set covering problem
- Edge Dominating Sets in Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees