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
graphs
on-line algorithm
graph
network
polymatroid
principal partition
strength
reinforcement
 
Description The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied. 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 continuously on-line. These are the first on-line algorithms for this problem. We invest O(\V\(3)\E\log\V\) time (equivalent to Omega(\V\) invocations of the fastest known algorithms for optimal reinforcement) in preprocessing the graph before the start of our algorithms. It is shown that the output of our on-line algorithms is as good as that of the off-line algorithms. Thus our algorithms are better than the fastest off-line algorithms in situations when a sequence of more than Omega(\V\) reinforcement problems need to be solved. The key idea is to make use of ideas underlying the theory of Principal Partition of a Graph. Our ideas are easily generalized to the general setting of polymatroid functions. We also present a new efficient algorithm for computation of the Principal Sequence of a graph.
 
Publisher KLUWER ACADEMIC PUBL
 
Date 2011-08-17T05:23:18Z
2011-12-26T12:55:22Z
2011-12-27T05:38:14Z
2011-08-17T05:23:18Z
2011-12-26T12:55:22Z
2011-12-27T05:38:14Z
2003
 
Type Article
 
Identifier JOURNAL OF COMBINATORIAL OPTIMIZATION, 7(1), 45-68
1382-6905
http://dx.doi.org/10.1023/A:1021994406231
http://dspace.library.iitb.ac.in/xmlui/handle/10054/9759
http://hdl.handle.net/10054/9759
 
Language en