Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition |
| |
Authors: | Sachin B. Patkar H. Narayanan |
| |
Affiliation: | (1) Department of Mathematics, Indian Institute of Technology, Bombay, Powai, Mumbai, 400 076, India;(2) Department of Electrical Engineering, Indian Institute of Technology, Bombay, Powai, Mumbai, 400 076, India |
| |
Abstract: | 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. |
| |
Keywords: | on-line algorithm graph network polymatroid Principal Partition strength reinforcement |
本文献已被 SpringerLink 等数据库收录! |
|