Relay placement for fault tolerance in wireless networks in higher dimensions

Abhishek Kashyap*, Samir Khuller, Mark Shayman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles).

Original languageEnglish (US)
Pages (from-to)206-215
Number of pages10
JournalComputational Geometry: Theory and Applications
Issue number4
StatePublished - May 2011


  • Fault tolerance
  • Network connectivity

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Relay placement for fault tolerance in wireless networks in higher dimensions'. Together they form a unique fingerprint.

Cite this