On the advice complexity of the online dominating set problem

被引：3
作者：
Bockenhauer, Hans-Joachim [1 ]
Hromkovicc, Juraj [1 ]
Krug, Sacha [1 ]
Unger, Walter [2 ]
机构：
[1] Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland
[2] Rhein Westfal TH Aachen, Dept Comp Sci, Aachen, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2021年 / 862卷
关键词：
Advice complexity; Online computation; Competitive analysis; Dominating set;
D O I：
10.1016/j.tcs.2021.01.022
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A dominating set S of a graph is a set of vertices such that each vertex is in S or has a neighbor in S. The goal of the dominating set problem is to find such a set of minimum cardinality. In the online setting, the graph is revealed vertex by vertex, together with edges to all previously revealed vertices. Advice complexity is a framework to measure the amount of information an online algorithm is lacking. Here, an online algorithm reads advice bits from an infinite binary tape prepared beforehand by an all-knowing oracle. The advice complexity is the total number of advice bits read during the computation. Besides giving some insight into what makes an online problem hard, advice complexity can also be used as a means for proving lower bounds on the competitive ratio achievable by randomized online algorithms. We analyze the advice complexity of the online dominating set problem. For general graphs, we show tight upper and lower bounds for optimality. Then, we use a result for c-competitiveness to prove that no randomized online algorithm can be better than n(1-epsilon)-competitive, for any epsilon > 0. Finally, we analyze the advice complexity of various graph classes for optimality. (C) 2021 The Author(s). Published by Elsevier B.V.
引用
收藏
页码：81 / 96
页数：16
相关论文
共 34 条
  • [21] Dorrigiv R, 2012, LECT NOTES COMPUT SC, V7676, P136
  • [22] Eidenbenz S, 2002, 380 ETH ZURICH
  • [23] ELIAS P, 1975, IEEE T INFORM THEORY, V21, P194, DOI 10.1109/TIT.1975.1055349
  • [24] Online computation with advice
    Emek, Yuval
    Fraigniaud, Pierre
    Korman, Amos
    Rosen, Adi
    [J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (24) : 2642 - 2656
  • [25] Gupta Sushmita, 2013, Structural Information and Communication Complexity. 20th International Colloquium, SIROCCO 2013. Revised Selected Papers: LNCS 8179, P55, DOI 10.1007/978-3-319-03578-9_5
  • [26] Hadlock F.O, 1975, P 6 SE C COMB GRAPH
  • [27] Haynes T.W., 2013, Fundamentals of Domination in Graphs, DOI DOI 10.1201/9781482246582
  • [28] Hromkovic J, 2010, LECT NOTES COMPUT SC, V6281, P24, DOI 10.1007/978-3-642-15155-2_3
  • [29] On-line algorithms for the dominating set problem
    King, GH
    Tzeng, WG
    [J]. INFORMATION PROCESSING LETTERS, 1997, 61 (01) : 11 - 14
  • [30] Komm D., 2016, INTRO ONLINE COMPUTA, DOI DOI 10.1007/978-3-319-42749-2
1234