Record Details

CONSTRUCTING RELIABLE COMMUNICATION-NETWORKS OF SMALL WEIGHT ONLINE

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title CONSTRUCTING RELIABLE COMMUNICATION-NETWORKS OF SMALL WEIGHT ONLINE
 
Creator CHANDRA, B
VISHWANATHAN, S
 
Subject spanning-trees
 
Description Suppose the vertices of a complete weighted graph are revealed to us one at a time, and we have to build a network with some desired properties on these vertices. We consider the cost of building a network which has these properties after the addition of each vertex and compare it to the cost incurred by an algorithm which builds a network that has the same properties only at the end, i.e., after all the vertices have been revealed. We examine online algorithms for constructing networks with three properties; high connectivity, low vertex degree, and small diameter, and evaluate these algorithms from the competitive perspective. We show that on n points drawn from any metric space, a greedy algorithm constructs a k-connected network with a competitive ratio of O(k(2) log n), and prove a lower bound of Omega(k log n) on the competitive ratio of any online algorithm. We also present an online algorithm with a competitive ratio of O(k(2) log n) to build a k-connected network with maximum vertex degree 3k and an online algorithm with a competitive ratio of O(k(2) log n) to build a k-connected network with a diameter no more than a constant times the diameter of the n points. (C) 1995 ,
 
Publisher ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS
 
Date 2011-07-12T18:06:23Z
2011-12-26T12:49:01Z
2011-12-27T05:34:40Z
2011-07-12T18:06:23Z
2011-12-26T12:49:01Z
2011-12-27T05:34:40Z
1995
 
Type Article
 
Identifier JOURNAL OF ALGORITHMS, 18(1), 159-175
0196-6774
http://dx.doi.org/10.1006/jagm.1995.1005
http://dspace.library.iitb.ac.in/xmlui/handle/10054/3408
http://hdl.handle.net/10054/3408
 
Language en