License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.52
URN: urn:nbn:de:0030-drops-82364
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8236/
Go to the corresponding LIPIcs Volume Portal


Kobayashi, Koji M.

Improved Bounds for Online Dominating Sets of Trees

pdf-format:
LIPIcs-ISAAC-2017-52.pdf (0.5 MB)


Abstract

The online dominating set problem is an online variant of the minimum dominating set problem, which is one of the most important NP-hard problems on graphs. This problem is defined as follows: Given an undirected graph G = (V, E), in which V is a set of vertices and E is a set of edges. We say that a set D \subseteq V of vertices is a dominating set of G if for each v \in V \setminus D, there exists a vertex u \in D such that {u, v} \in E. The vertices are revealed to an online algorithm one by one over time. When a vertex is revealed, edges between the vertex and vertices revealed in the past are also revealed. A revelaed subtree is connected at any time. Immediately after the revelation of each vertex, an online algorithm can choose vertices which were already revealed irrevocably and must maintain a dominating set of a graph revealed so far. The cost of an algorithm on a given tree is the number of vertices chosen by it, and its objective is to minimize the cost. Eidenbenz (Technical report, Institute of Theoretical Computer Science, ETH Zurich, 2002) and Boyar et al. (SWAT 2016) studied the case in which given graphs are trees. They designed a deterministic online algorithm whose competitive ratio is at most three, and proved that a lower bound on the competitive ratio of any deterministic algorithm is two. In this paper, we also focus on trees. We establish a matching lower bound for any deterministic algorithm. Moreover, we design a randomized online algorithm whose competitive ratio is at most 5/2 = 2.5, and show that the competitive ratio of any randomized algorithm is at least 4/3 \approx 1.333.

BibTeX - Entry

@InProceedings{kobayashi:LIPIcs:2017:8236,
  author =	{Koji M. Kobayashi},
  title =	{{Improved Bounds for Online Dominating Sets of Trees}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8236},
  URN =		{urn:nbn:de:0030-drops-82364},
  doi =		{10.4230/LIPIcs.ISAAC.2017.52},
  annote =	{Keywords: online algorithm, dominating set, competitive analysis, tree graph, randomized algorithm}
}

Keywords: online algorithm, dominating set, competitive analysis, tree graph, randomized algorithm
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 04.12.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI