Online Dominating Set

DOI10.4230/LIPICS.SWAT.2016.21MaRDI QIDQ5369523zbMATH OpenOpenAlexFDO

Authors Michal Kotrbčík, Kim S. Larsen, Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt

Publication date 17 October 2017

Full work available at URL https://arxiv.org/abs/1604.05172

zbMATH Keywords

competitive analysisconnected graphsdominating setgraph classesonline algorithms

Mathematics Subject Classification ID

Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Abstract: This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.

Recommendations

• Online dominating set
• scientific article; zbMATH DE number 1302187
• Improved bounds for online dominating sets of trees
• The online set cover problem
• The online set cover problem
• scientific article; zbMATH DE number 1696636
• On the advice complexity of the online dominating set problem
• The online set aggregation problem
• Algorithms and Models for the Web-Graph
• Online and dynamic algorithms for set cover

Cited in

(5)

• Online dominating set
• scientific article; zbMATH DE number 1302187 (Why is no real title available?)
• Improved bounds for online dominating sets of trees
• Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems
• Delaying decisions and reservation costs

This page was built for publication: Online Dominating Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369523)