Approximation hardness of dominating set problems in bounded degree graphs
- 1 November 2008
- journal article
- Published by Elsevier in Information and Computation
- Vol. 206 (11) , 1264-1275
Abstract
No abstract availableThis publication has 14 references indexed in Scilit:
- Approximation hardness of edge dominating set problemsJournal of Combinatorial Optimization, 2006
- On the approximability of the maximum induced matching problemJournal of Discrete Algorithms, 2005
- Bipartite Domination and Simultaneous Matroid CoversSIAM Journal on Discrete Mathematics, 2003
- The importance of being biased2002
- Some optimal inapproximability resultsJournal of the ACM, 2001
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Improved approximations of independent dominating set in bounded degree graphsLecture Notes in Computer Science, 1997
- A short note on the approximability of the maximum leaves spanning tree problemInformation Processing Letters, 1994
- Approximating the minimum maximal independence numberInformation Processing Letters, 1993
- On approximating the minimum independent dominating setInformation Processing Letters, 1991