Abstract
The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E,w) is well-studied [1],[2],[3],[6],[7],[9]. 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 continuosly online. These are first on-line algortithms 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 that 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 the theory of Principal Partition of a Graph. Our results can be easily generalized to the general setting of principal partition of nondecreasing submodular functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barahona, F.: Separating from the dominant of spanning tree polytope,Oper. Res. Letters, vol. 12, 1992, pp.201–203.
Cheng, E. and Cunningham, W.: A faster algorithm for computing thestrength of a network, Information Processing Letters, vol. 49, 1994, pp.209–212.
Cunningham, W.: Optimal attack and reinforcement of a network, JACM,vol. 32, no. 3, 1985, pp.549–561.
Dinkelbach, W.: On nonlinear fractional programming, Management Sci.,vol. 13, 1967, pp.492–498.
Edmonds, J.: Submodular functions, matroids and certain polyhedra, Proc.Calgary Intl. conference on Combinatorial Structures, 1970, pp.69–87.
Fujishige, S.:Submodular Functions and Optimization, Annals of DiscreteMathematics, North Holland, 1991.
Gabow, H.N.: Algorithms for graphic polymatroids and parametric s-sets J.Algorithms, vol. 26, 1998, pp.48–86.
Gallo, G., Grigoriadis, M. and Tarjan, R.E.: A fast parametric network flow algorithm, SIAM J. of Computing, vol. 18, 1989, pp.30–55.
Gusfield, D.: Computing the strength of a graph, SIAM J. of Computing,vol. 20, 1991, pp.639–654.
Imai, H.: Network flow algorithms for lower truncated transversal polymatroids,J. of the Op. Research Society of Japan, vol. 26, 1983, pp. 186–210.
Iri, M. and Fujishige, S.: Use of matroid theory in operations research, circuitsand systems theory, Int. J. Systems Sci.,vol. 12, no. 1, 1981, pp. 27–54.
Itai, A. and Rodeh, M.: The multi-tree approach to reliability in distributednetworks, in Proc. 25th ann. symp. FOCS, 1984, pp. 137–147.
Narayanan, H.:Theory of matroids and network analysis, Ph.D. thesis, Departmentof Electrical Engineering, I.I.T. Bombay, 1974.
Narayanan, H.: The principal lattice of partitions of a submodular function,Linear Algebra and its Applications, 144, 1991, pp. 179–216.
Narayanan, H., Roy, S. and Patkar, S.B.: Approximation Algorithms formin-k-overlap Problems, using the Principal Lattice of Partitions Approach,J. of Algorithms, vol. 21, 1996, pp. 306–330.
Narayanan, H.: Submodular Functions and Electrical Networks, Annals ofDiscrete Mathematics-54, North Holland, 1997.
Patkar, S. and Narayanan, H.: Principal lattice of partitions of submodularfunctions on graphs: fast algorithms for principal partition and genericrigidity, in Proc. of the 3rd ann. Int. Symp. on Algorithms and Computation,(ISAAC), LNCS-650, Japan, 1992, pp. 41–50.
Patkar, S. and Narayanan, H.: Fast On-line/Off-line Algorithms for OptimalReinforcement of a Network and its Connections with Principal Partition,Technical Report, Industrial Mathematics Group, Department of Mathematics,IIT Bombay, available from authors via e-mail, 2000.
Tomizawa, N.: Strongly irreducible matroids and principal partition of amatroid into strongly irreducible minors (in Japanese), Transactions of theInstitute of Electronics and Communication Engineers of Japan, vol. J59A,1976, pp. 83–91.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patkar, S.B., Narayanan, H. (2000). Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition. In: Kapoor, S., Prasad, S. (eds) FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2000. Lecture Notes in Computer Science, vol 1974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44450-5_7
Download citation
DOI: https://doi.org/10.1007/3-540-44450-5_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41413-1
Online ISBN: 978-3-540-44450-3
eBook Packages: Springer Book Archive