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.
