Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a
given range assignment is either an undirected graph referred to as the bidirectional topology, or a directed graph referred
to as the unidirectional topology. The Min-Power Bidirectional (resp., Unidirectional)
k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint that the produced bidirectional
(resp. unidirectional) topology is
k-vertex connected. Similarly, the Min-Power Bidirectional (resp., Unidirectional)
k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the produced bidirectional
(resp., unidirectional) topology is
k-edge connected.
The Min-Power Bidirectional Biconnectivity problem and the Min-Power Bidirectional Edge-Biconnectivity problem have been studied
by Lloyd et al. [23]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [18],
which we refer to as
Algorithm KR, has an approximation ratio of at most 2(2 – 2/
n)(2 + 1/
n) for Min-Power Bidirectional Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [19],
which we refer to as
Algorithm KV, has an approximation ratio of at most 8(1 – 1/
n) for Min-Power Bidirectional Edge-Biconnectivity.
In this paper, we first establish the NP-hardness of Min-Power Bidirectional (Edge-) Biconnectivity. Then we show that
Algorithm KR has an approximation ratio of at most 4 for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity,
and
Algorithm KV has an approximation ratio of at most 2
k for both Min-Power Bidirectional
k-Edge Connectivity and Min-Power Unidirectional
k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Bidirectional Biconnectivity
and Min-Power Unidirectional Biconnectivity. This new algorithm applies only to Euclidean instances, but is best suited for
distributed implementation.
A preliminary version of this work appeared in the proceedings of the 2nd International Conference on AD-HOC Network and Wireless
(Adhoc-Now 2003).
Research performed in part while visiting the Max-Plank-Institut fur Informatik.
Gruia Calinescu is an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He held postdoc or visiting
researcher positions at DIMACS, University of Waterloo, and Max-Plank Institut fur Informatik. Gruia has a Diploma from University
of Bucharest and a Ph.D. from Georgia Insitute of Technology. His research interests are in the area of algorithms.
Peng-Jun Wan has joined the Computer Science Department at Illinois Institute of Technology in 1997 and has been an Associate Professor
since 2004. He received his Ph.D. in Computer Science from University of Minnesota in 1997, M.S. in Operations Research and
Control Theory from Chinese Academy of Science in 1993, and B.S. in Applied Mathematics from Tsinghua University in 1990.
His research interests include optical networks and wireless networks.
相似文献