The erratum acknowledges an omission of one co-author, Samir Khuller, in the article "Approximation Algorithms for Connected Dominating Sets" published in *Algorithmica* (20:4, April 1998). The publisher apologizes for any inconvenience caused and requests that all author names be used when referring to the article.The erratum acknowledges an omission of one co-author, Samir Khuller, in the article "Approximation Algorithms for Connected Dominating Sets" published in *Algorithmica* (20:4, April 1998). The publisher apologizes for any inconvenience caused and requests that all author names be used when referring to the article.