Fast On-line/Off-line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition

H. Narayanan Sachin B. Patkar

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


Abstract: The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V,E) 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 continously on-line. These are first on-line algorithms 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 than 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 ideas underlying the theory of Principal Partition of a Graph. Our results can be easily generalized to the general setting of principal partition of submodular functions. Keywords: Strength and optimal reinforcement of a graph, on-line algorithms, principal partition, submodular functions.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems