Please use this identifier to cite or link to this item:
Title: Approximation algorithms for minimum power k backbone node r -connected subgraph problem in wireless sensor networks
Authors: Shetty, D.P.
Lakshmi, M.P.
Issue Date: 2019
Citation: Discrete Mathematics, Algorithms and Applications, 2019, Vol., , pp.-
Abstract: The minimum power assignment problem in a Wireless Sensor Network (WSN) is to assign transmission range to the nodes of the network with specified connectivity constraints minimizing the total power. This problem is termed as Strong Minimum Energy Topology (SMET) problem. Fault tolerance addresses the issue of a node or link failure in a WSN. So, with an objective of achieving high connectivity, we consider SMET problem with an additional property, i.e., the resultant network must satisfy the property of two or high connectivity. Minimum Power r-Connected Subgraph (MPrCS) problem is to contrive an r-connected network with minimum power. Minimum Power 2-Connected Subgraph (MP2CS) problem is proved to be NP-hard. Minimum Power k Backbone node r-Connected Subgraph (MPkBrCS) problem is a special case of MPrCS problem, which seeks a power assignment satisfying r-connectivity with k backbone nodes. We study MPkBrCS problem for k backbone nodes, r-connectivity and derive the approximation ratios. We also propose an algorithm of approximation ratio n+2 2, for Minimum Power k Backbone node 3-Connected Subgraph (MPkB3CS) problem for k = 2 that runs in O(n4) time and generalize for the case r = k + 1 for any k and r. 2020 World Scientific Publishing Company.
Appears in Collections:1. Journal Articles

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.