Relay node placement under budget constraint

Chenyang Zhou, Anisha Mazumder, Arun Das, Kaustav Basu, Navid Matin-Moghaddam, Saharnaz Mehrani, Arunabha Sen

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


The relay node placement problem in the wireless sensor network domain has been studied extensively. But under a fixed budget, it may be impossible to procure the minimum number of relay nodes needed to design a connected network of sensor and relay nodes. Nevertheless, one would still like to design a network with high level of connectedness, or low disconnectedness. In this paper, we introduce the notion of 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” subject to a fixed budget constraint.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalPervasive and Mobile Computing
StatePublished - Feb 1 2019


  • Approximation algorithms
  • Disconnectivity
  • Inapproximability
  • Maximal connectedness
  • NP-complete

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Applied Mathematics


Dive into the research topics of 'Relay node placement under budget constraint'. Together they form a unique fingerprint.

Cite this