Tighter bounds for the minimum energy broadcasting problem

被引：15
|
作者：
Navarra, A [1 ]
机构：
[1] Univ Aquila, Dept Comp Sci, I-67100 Laquila, Italy
来源：
Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks | 2005年
关键词：
D O I：
10.1109/WIOPT.2005.51
中图分类号：
TN [电子技术、通信技术];
学科分类号：
0809 ;
摘要：
In this paper we present a new upper bound on the approximation ratio of the Minimum Spanning Tree heuristic for the basic problem on Ad-Hoc Networks given by the Minimum-Energy Broadcast Routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound [3].
引用
收藏
页码：313 / 322
页数：10
相关论文
共 50 条
  • [1] Tighter bounds on the minimum broadcast time
    Haugland, Dag
    DISCRETE OPTIMIZATION, 2024, 51
  • [2] TIGHTER BOUNDS ON A HEURISTIC FOR A PARTITION PROBLEM
    LEUNG, JYT
    WEI, WD
    INFORMATION PROCESSING LETTERS, 1995, 56 (01) : 51 - 57
  • [3] Improved Approximation Results for the Minimum Energy Broadcasting Problem
    Michele Flammini
    Ralf Klasing
    Alfredo Navarra
    Stephane Perennes
    Algorithmica, 2007, 49 : 318 - 336
  • [4] 3-Dimensional minimum energy broadcasting problem
    Navarra, Alfredo
    AD HOC NETWORKS, 2008, 6 (05) : 734 - 743
  • [5] Improved approximation results for the minimum energy broadcasting problem
    Flammini, Michele
    Klasing, Ralf
    Navarra, Alfredo
    Perennes, Stephane
    ALGORITHMICA, 2007, 49 (04) : 318 - 336
  • [6] TIGHTER TIME-BOUNDS ON FAULT-TOLERANT BROADCASTING AND GOSSIPING
    GARGANO, L
    NETWORKS, 1992, 22 (05) : 469 - 486
  • [7] Tighter time bounds on broadcasting in torus networks in presence of dynamic faults
    De Marco, Gianluca
    Parallel Processing Letters, 2000, 10 (01): : 39 - 49
  • [8] A localized algorithm for minimum-energy broadcasting problem in MANET
    Peng, C
    Shen, H
    GRID AND COOPERATIVE COMPUTING - GCC 2005, PROCEEDINGS, 2005, 3795 : 971 - 977
  • [9] Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
    Li, Minming
    Wan, Peng-Jun
    Yao, Frances
    ALGORITHMICA, 2011, 61 (04) : 1000 - 1021
  • [10] Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
    Minming Li
    Peng-Jun Wan
    Frances Yao
    Algorithmica, 2011, 61 : 1000 - 1021
12345