1 Search Results for "Kobayashi, Koji M."

Document
DOI: 10.4230/LIPIcs.ISAAC.2017.52
Improved Bounds for Online Dominating Sets of Trees

Authors: Koji M. Kobayashi

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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.
Cite as

Koji M. Kobayashi. Improved Bounds for Online Dominating Sets of Trees. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kobayashi:LIPIcs.ISAAC.2017.52,
  author =	{Kobayashi, Koji M.},
  title =	{{Improved Bounds for Online Dominating Sets of Trees}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.52},
  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}
}
  • Refine by Author
  • 1 Kobayashi, Koji M.

  • Refine by Classification

  • Refine by Keyword
  • 1 competitive analysis
  • 1 dominating set
  • 1 online algorithm
  • 1 randomized algorithm
  • 1 tree graph

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact