Loading...
Please wait, while we are loading the content...
Similar Documents
Online Dominating Set and Variations on Restricted Graph Classes
| Content Provider | CiteSeerX |
|---|---|
| Author | Eidenbenz, Stephan |
| Abstract | 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Restricted Graph Class Online Dominating Set Degree Graph Optimum Competitive Ratio Minimum Connected Dominating Set Minimum Independent Dominating Set Online Version Minimum Dominating Set Easy-to-implement Online Strategy Certain Graph Class Insertion Step Unit Disk Graph Input Graph |
| Content Type | Text |