A LOWER BOUND ON PROBABILISTIC ALGORITHMS FOR DISTRIBUTIVE RING COLORING

被引：72
作者：
NAOR, M
机构：
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1991年 / 4卷 / 03期
关键词：
DISTRIBUTED COMPUTATION; PROBABILISTIC ALGORITHMS; GRAPH COLORING;
D O I：
10.1137/0404036
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least 1/2 log * n - 2 rounds, otherwise the probability that all processors are colored legally is less than 1/2. A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin [Inform. and Control, 70 (1986), pp. 32-53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331-335].
引用
收藏
页码：409 / 412
页数：4
相关论文
共 50 条
  • [31] Exponential-Time Quantum Algorithms for Graph Coloring Problems
    Kazuya Shimizu
    Ryuhei Mori
    Algorithmica, 2022, 84 : 3603 - 3621
  • [32] Dominating set based exact algorithms for 3-coloring
    Narayanaswamy, N. S.
    Subramanian, C. R.
    INFORMATION PROCESSING LETTERS, 2011, 111 (06) : 251 - 255
  • [33] Exponential-Time Quantum Algorithms for Graph Coloring Problems
    Shimizu, Kazuya
    Mori, Ryuhei
    ALGORITHMICA, 2022, 84 (12) : 3603 - 3621
  • [34] Implementation of Algorithms for L(2,1)-Coloring Problems
    Vollala, Satyanarayana
    Indrajeet, S.
    Joshi, Amit D.
    Tamizharasan, P. S.
    Jose, Jobin
    2017 8TH INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND NETWORKING TECHNOLOGIES (ICCCNT), 2017,
  • [35] Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
    Assadi, Sepehr
    Chakrabarti, Amit
    Ghosh, Prantar
    Stoeckl, Manuel
    PROCEEDINGS OF THE 42ND ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, PODS 2023, 2023, : 141 - 153
  • [36] An asynchronous P system using branch and bound for minimum graph coloring
    Umetsu, Kotaro
    Fujiwara, Akihiro
    2019 SEVENTH INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING WORKSHOPS (CANDARW 2019), 2019, : 242 - 248
  • [37] A tight bound for conflict-free coloring in terms of distance to cluster
    Bhyravarapu, Sriram
    Kalyanasundaram, Subrahmanyam
    DISCRETE MATHEMATICS, 2022, 345 (11)
  • [38] Co-learning of Functions by Probabilistic Algorithms
    Kucevalovs, Ilja
    Balodis, Kaspars
    Freivalds, Rusins
    PROCEEDINGS OF THE 2ND INTERNATIONAL SYMPOSIUM ON COMPUTER, COMMUNICATION, CONTROL AND AUTOMATION, 2013, 68 : 71 - 73
  • [39] Graph coloring algorithms for multi-core and massively multithreaded architectures
    Catalyuerek, Uemit V.
    Feo, John
    Gebremedhin, Assefaw H.
    Halappanavar, Mahantesh
    Pothen, Alex
    PARALLEL COMPUTING, 2012, 38 (10-11) : 576 - 594
  • [40] PROBABILISTIC ALGORITHMS FOR LEAST MEDIAN OF SQUARES REGRESSION
    JOSS, J
    MARAZZI, A
    COMPUTATIONAL STATISTICS & DATA ANALYSIS, 1990, 9 (01) : 123 - 133
12345