Online dominating set and variations on restricted graph classes
Stephan Eidenbenz · Repository for Publications and Research Data (ETH Zurich) · 2002
We study online versions of Minimum Dominating Set, Minimum Connected Dominating Set, and Minimum Independent Dominating Set, where we restrict the input graphs to belong to a certain graph class after each insertion step. Weshow that straight-forward and easy-to-implement online strategies achieve optimum or nearly optimum competitive ratios for trees, unit disk graphs, and bounded degree graphs for standard and independent dominating sets. For connected dominating sets, our results are not tight and thus provide challenges for future research.