id: 04174332
dt: j
an: 04174332
au: Irving, Robert W.
ti: On approximating the minimum independent dominating set.
so: Inf. Process. Lett. 37, No.4, 197-200 (1991).
py: 1991
pu: Elsevier Sciences Publishers (North-Holland), Amsterdam
la: EN
cc: 
ut: computational complexity; combinatorial problems; NP-hard graph problems;
    polynomial-time approximation algorithm
ci: 
li: doi:10.1016/0020-0190(91)90188-N
ab: Summary: The problem of determining a smallest independent dominating set
    in a graph, or equivalently, a smallest maximal independent set, is
    NP-hard. We show that, unless $P=NP$, no polynomial-time approximation
    algorithm for this problem can guarantee to find an independent
    dominating set with size within a factor of K of the optimal, where K
    is any fixed constant $>1$. The result holds even if the graph in
    question is restricted to be bipartite.
rv: