Brief Announcement: A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model

被引：0
|
作者：
Khan, Maleq [1 ]
Pandurangan, Gopal [3 ,4 ]
Pei, Guanhong [1 ]
Vullikanti, Anil Kumar S. [1 ,2 ]
机构：
[1] Virginia Tech, Virginia Bioinformat Inst, Blacksburg, VA 24061 USA
[2] Virginia Tech, Dept Comp Sci, Blacksburg, VA 24061 USA
[3] Nanyang Technol Univ, Div Math Sci, Nanyang, Singapore
[4] Brown Univ, Dept Comp Sci, Providence, RI 02912 USA
来源：
DISTRIBUTED COMPUTING, DISC 2012 | 2012年 / 7611卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study the minimum spanning tree (MST) construction problem in wireless networks under the physical interference model based on SINR constraints. We develop the first distributed (randomized) O(p)-approximation algorithm for MST, with the running time of O(D log n) (with high probability) where D denotes the diameter of the disk graph obtained by using the maximum possible transmission range, and i = log ddmax denotes the "distance diversity" w.r.t. the largest and smallest distances between two nodes. (When ddmax is npolynomial, i = O(log n).)
引用
收藏
页码：409 / +
页数：2
相关论文
共 50 条
  • [1] A fast distributed approximation algorithm for minimum spanning trees
    Khan, Maleq
    Pandurangan, Gopal
    DISTRIBUTED COMPUTING, PROCEEDINGS, 2006, 4167 : 355 - +
  • [2] A fast distributed approximation algorithm for minimum spanning trees
    Maleq Khan
    Gopal Pandurangan
    Distributed Computing, 2008, 20 : 391 - 402
  • [3] A fast distributed approximation algorithm for minimum spanning trees
    Khan, Maleq
    Pandurangan, Gopal
    DISTRIBUTED COMPUTING, 2008, 20 (06) : 391 - 402
  • [4] A distributed approximation algorithm for the minimum degree minimum weight spanning trees
    Lavault, Christian
    Valencia-Pabon, Mario
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2008, 68 (02) : 200 - 208
  • [5] Brief Announcement: Energy-Optimal Distributed Algorithms for Minimum Spanning Trees
    Choi, Yongwook
    Khan, Maleq
    Kumar, V. S. Anil
    Pandurangan, Gopal
    SPAA'08: PROCEEDINGS OF THE TWENTIETH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2008, : 188 - +
  • [6] Brief Announcement: Distributed Reconfiguration of Spanning Trees
    Gupta, Siddharth
    Kumar, Manish
    Pai, Shreyas
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS (SSS 2022), 2022, 13751 : 346 - 351
  • [7] Brief Announcement: Almost-Tight Approximation Distributed Algorithm for Minimum Cut
    Nanongkai, Danupon
    PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, : 382 - 384
  • [8] Brief Announcement: Fast and Simple Node Coloring in the SINR Model
    Fuchs, Fabian
    PODC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2015, : 139 - 141
  • [9] Fast Approximation Algorithms for Computing Constrained Minimum Spanning Trees
    Yao, Pei
    Guo, Longkun
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I, 2017, 10627 : 103 - 110
  • [10] Brief Announcement: Minimum Spanning Trees and Cone-Based Topology Control
    Cornejo, Alejandro
    Lynch, Nancy
    PODC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2009, : 296 - 297
12345