Paper Info
Title
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs
Abstract
We consider the problem of computing an optimal range assignment in a wireless network which allows a specified source station to perform a broadcast operation. In particular, we consider this problem as a special case of the following more general combinatorial optimization problem, called Minimum Energy Consumption Broadcast Subgraph (in short, MECBS): Given a weighted directed graph and a specified source node, find a minimum cost range assignment to the nodes, whose corresponding transmission graph contains a spanning tree rooted at the source node. We first prove that MECBS is not approximable within a sub-logarithmic factor (unless P=NP). We then consider the restriction of MECBS to wireless networks and we prove several positive and negative results, depending on the geometric space dimension and on the distance-power gradient. The main result is a polynomial-time approximation algorithm for the NP-hard case in which both the dimension and the gradient are equal to 2: This algorithm can be generalized to the case in which the gradient is greater than or equal to the dimension.
Year
Venue
Keywords
2001
STACS
specified source station,special case,specified source node,wireless network,np-hard case,computing minimum energy consumption,corresponding transmission graph,general combinatorial optimization problem,geometric space dimension,broadcast subgraphs,source node,distance-power gradient,directed graph,spanning tree
Field
DocType
ISBN
Discrete mathematics,Approximation algorithm,Wireless network,Combinatorics,Computer science,Directed graph,Combinatorial optimization,Spanning tree,Time complexity,Special case,Computational complexity theory
Conference
3-540-41695-1
Citations 
PageRank 
References 
142
9.53
13
Authors
5
Search Limit
100142
Name
Order
Citations
PageRank
Andrea E. F. Clementi1116885.30
Pierluigi Crescenzi2100295.31
Paolo Penna320617.77
Gianluca Rossi423521.60
Paola Vocca522524.79