×

Finding the most vital node of a shortest path. (English) Zbl 1044.68132

Summary: In an undirected, 2-node connected graph \(G=(V,E)\) with positive real edge lengths, the distance between any two nodes \(r\) and \(s\) is the length of a shortest path between \(r\) and \(s\) in \(G\). The removal of a node and its incident edges from \(G\) may increase the distance from \(r\) to \(s\). A most vital node of a given shortest path from \(r\) to \(s\) is a node (other than \(r\) and \(s\)) whose removal from \(G\) results in the largest increase of the distance from \(r\) to \(s\). In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. In this paper, we show that this problem can be solved in O(\(m+n \log n)\) time and O(\(m\)) space, where \(m\) and \(n\) denote the number of edges and the number of nodes in \(G\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ball, M. O.; Golden, B. L.; Vohra, R. V., Finding the most vital arcs in a network, Oper. Res. Lett., 8, 73-76 (1989) · Zbl 0679.90086
[2] A. Bar-Noy, S. Khuller, B. Schieber, The complexity of finding most vital arcs and nodes, TR CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995.; A. Bar-Noy, S. Khuller, B. Schieber, The complexity of finding most vital arcs and nodes, TR CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995.
[3] Corley, H. W.; Sha, D. Y., Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 157-160 (1982) · Zbl 0488.90069
[4] Dijkstra, E. W., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[5] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 3, 596-615 (1987) · Zbl 1412.68048
[6] J. Hershberger, S. Suri, Vickrey prices and shortest paths: what is an edge worth? Proc. 42nd Annu. IEEE Symp. on Foundations of Computer Science (FOCS’01), 2001, pp. 252-260.; J. Hershberger, S. Suri, Vickrey prices and shortest paths: what is an edge worth? Proc. 42nd Annu. IEEE Symp. on Foundations of Computer Science (FOCS’01), 2001, pp. 252-260.
[7] Malik, K.; Mittal, A. K.; Gupta, S. K., The \(k\) most vital arcs in the shortest path problem, Oper. Res. Lett., 8, 223-227 (1989) · Zbl 0669.90090
[8] Nardelli, E.; Proietti, G.; Widmayer, P., Finding the detour-critical edge of a shortest path between two nodes, Inform. Process. Lett., 67, 1, 51-54 (1998) · Zbl 1339.68210
[9] Nardelli, E.; Proietti, G.; Widmayer, P., A faster computation of the most vital edge of a shortest path between two nodes, Inform. Process. Lett., 79, 2, 81-85 (2001) · Zbl 1013.68134
[10] Nisan, N., (Algorithms for selfish agents, Proc. 16th Symp. on Theoretical Aspects of Computer Science (STACS’99), Lecture Notes in Comput. Sci., vol. 1563 (1999), Springer: Springer Berlin), 1-15
[11] N. Nisan, A. Ronen, Algorithmic mechanism design, Proc. 31st Annu. ACM Symp. on Theory of Computing (STOC’99), 1999, pp. 129-140.; N. Nisan, A. Ronen, Algorithmic mechanism design, Proc. 31st Annu. ACM Symp. on Theory of Computing (STOC’99), 1999, pp. 129-140. · Zbl 1346.68246
[12] Rosenschein, J. S.; Zlotkin, G., Rules of EncounterDesigning Conventions for Automated Negotiation Among Computers (1994), MIT Press: MIT Press Cambridge, MA
[13] Tarjan, R. E., Efficiency of a good but not linear set union algorithm, J. ACM, 22, 215-225 (1975) · Zbl 0307.68029
[14] S. Venema, H. Shen, F. Suraweera, A parallel algorithm for the single most vital vertex problem with respect to single source shortest paths, Online Proc. First Internat. Conf. on Parallel and Distributed Computing, Applications and Technologies (PDCAT’2000), Chapter 22, http://www2.comp.polyu.edu.hk/PDCAT2000/publish.html; S. Venema, H. Shen, F. Suraweera, A parallel algorithm for the single most vital vertex problem with respect to single source shortest paths, Online Proc. First Internat. Conf. on Parallel and Distributed Computing, Applications and Technologies (PDCAT’2000), Chapter 22, http://www2.comp.polyu.edu.hk/PDCAT2000/publish.html · Zbl 0900.68240
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.