Assign ranges in general ad-hoc networks

Janka Chlebikova, Deshi Ye, Hu Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper we study the Minimum Range Assignment problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the Minimum Range Assignment problem, where the communication graph has to fulfill either the h-strong connectivity condition (Min-Range( h -SC)) or the h-broadcast condition (Min-Range( h -B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(log n)-approximation algorithms for Min-Range( h -SC) and Min-Range( h -B), which improves the previous best ratios O(log n loglog n) and O(n 2log n loglog n), respectively [21]. The result for Min-Range( h -B) matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient α is sufficiently small, the approximation ratio is improved to O((loglog n) α ).
Original languageEnglish
Title of host publicationAlgorithmic applications in management
Subtitle of host publicationfirst international conference, AAIM 2005, Xian, China, June 22-25, 2005, proceedings
EditorsNimrod Megiddo, Yinfeng Xu, Binhai Zhu
ISBN (Electronic)9783540324409
ISBN (Print)9783540262244
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Assign ranges in general ad-hoc networks'. Together they form a unique fingerprint.

Cite this