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

摘要

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 Ω(|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 Ω(|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.