## Abstract

The relay node placement problem in the wireless sensor network domain has been studied extensively over the past few years. The objective of most of these problems, is to place the fewest number of relay nodes in the deployment area so that the network, formed by the sensor and the relay nodes, is connected. Under the fixed budget scenario, the expense involved in procuring the minimum number of relay nodes to make the network connected, may exceed the budget. Although, in this case, one must give up the idea of having of a connected network but one would still like to design a network with a high level of connectedness, or a low level of disconnectedness. In this paper, we introduce the notion of disconnectivity, a measure of the "connectedness" of a disconnected graph. We study a family of problems whose goal is to design a network with "maximal connectedness" or "minimal disconnectedness", subject to a fixed budget constraint. We show that all problems in this family are NP-Complete and present an approximation algorithm with a performance bound of 1/10 for the problem that maximizes the size of the largest connected components, and inapproximability results for the problem that maximizes the size of the smallest connected component and the problem that minimizes the number of connected components. In addition, we present future direction of our research on this topic.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018 |

Publisher | Association for Computing Machinery |

Volume | Part F133180 |

ISBN (Electronic) | 9781450363723 |

DOIs | |

State | Published - Jan 4 2018 |

Event | 19th International Conference on Distributed Computing and Networking, ICDCN 2018 - Varanasi, India Duration: Jan 4 2018 → Jan 7 2018 |

### Other

Other | 19th International Conference on Distributed Computing and Networking, ICDCN 2018 |
---|---|

Country/Territory | India |

City | Varanasi |

Period | 1/4/18 → 1/7/18 |

## Keywords

- Approximation Algorithms
- Disconnectivity
- Inapproximability
- Maximal Connectedness
- NP-Complete

## ASJC Scopus subject areas

- Human-Computer Interaction
- Computer Networks and Communications
- Computer Vision and Pattern Recognition
- Software