Record Details

Fast on-line/off-line algorithms for optimal reinforcement of a network and its connections with principal partition

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Fast on-line/off-line algorithms for optimal reinforcement of a network and its connections with principal partition
 
Creator PATKAR, SB
NARAYANAN, H
 
Subject lattice
polymatroids
strength
 
Description The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied [1,2,3,6,7,9]. In this paper, we present fast (sequential linear time and parallel logarithmic time) on-line algorithms for optimally reinforcing the graph when the reinforcement material is available continuosly online. These are first on-line algortithms for this problem. Although we invest some time in preprocessing the graph before the start of our algorithms, it is also shown that the output of our on-line algorithms is as good as that of the off-line algorithms, making our algorithms viable alternatives to the fastest off-line algorithms in situtations when a sequence of more than O(/V/) reinforcement problems need to be solved. In such a situation the time taken for preprocessing the graph is less that the time taken for all the invocations of the fastest off-line algorithms. Thus our algorithms are also efficient in the general sense. The key idea is to make use of the theory of Principal Partition of a Graph. Our results can be easily generalized to the general setting of principal partition of nondecreasing submodular functions.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T13:34:20Z
2011-12-15T09:11:10Z
2011-10-23T13:34:20Z
2011-12-15T09:11:10Z
2000
 
Type Article; Proceedings Paper
 
Identifier FST TCS 2000: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, PROCEEDINGS,1974,94-105
3-540-41413-4
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15142
http://hdl.handle.net/100/1898
 
Source 20th Conference on Foundations of Software Technology and Theoretical Computer Science,NEW DELHI, INDIA,DEC 13-15, 2000
 
Language English