The most vital edges in the minimum spanning tree problem. (English) Zbl 0768.68051
Summary: Let \(G(N;A)\) be a connected, undirected and weighted network with node set \(N\) and edge set \(A\). Suppose that there is an available budget to spend on removing edges and there is a removal cost associated with each edge. The most vital edges problem is to find a set of edges such that the total removal cost is not greater than the available budget and whose removal from \(G(N;A)\) results in the greatest increase in the total weight of a minimum spanning tree. We show that this problem is NP-hard and propose a branch and bound algorithm to solve it.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C05 | Trees |
Keywords:
computational complexity; weighted network; most vital edges; minimum spanning tree; NP-hard; branch and bound algorithmReferences:
| [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] | Chern, M.-S.; Jan, R.-H.; Lee, K.-L., The most vital links in network reliability analysis, (Working paper (1989), Dept. of Industrial Engineering, National Tsing Hua University: Dept. of Industrial Engineering, National Tsing Hua University Taiwan, ROC), presented at the CORS/TIMS/ORSA Joint National Meeting 1989, Vancouver, Canada |
| [3] | Chern, M.-S.; Lin, K.-C., The most vital arcs and interdiction problems in network programming (II), (Research Rept. NSC-81-0415-E007-03 (1992), National Science Council: National Science Council Taiwan, ROC) |
| [4] | Corley, H. W.; Sha, D. Y., Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 157-160 (1982) · Zbl 0488.90069 |
| [5] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [6] | Gomory, R. E.; Hu, T. C., Multi-terminal network flows, J. SIAM, 9, 551-570 (1961) · Zbl 0112.12405 |
| [7] | Horowitz, E.; Sahni, S., Fundamentals of Computer Algorithms (1978), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0442.68022 |
| [8] | Hsu, L.-H.; Jan, R.-H.; Lee, Y.-C.; Hung, C.-N.; Chern, M.-S., Finding the most vital edge with respect to minimum spanning tree in weighted graphs, Inform. Process. Lett., 39, 5, 277-281 (1991) · Zbl 0749.68043 |
| [9] | Lubore, S. H.; Ratliff, H. D.; Sicilia, G. T., Determining the most vital link in a flow network, Naval Res. Logist. Quart., 18, 497-502 (1971) · Zbl 0241.90020 |
| [10] | 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 |
| [11] | Malik, K.; Mittal, A. K.; Gupta, S. K., Erratum: The \(k\) most vital arcs in the shortest path problem, Oper. Res. Lett., 9, 283 (1990) |
| [12] | Ratliff, H. D.; Sicilia, G. T.; Lubore, S. H., Finding the \(n\) most vital links in flow networks, Management Sci., 21, 531-539 (1975) · Zbl 0311.90073 |
| [13] | Tarjan, R. E., Data Structures and Network Algorithms (1983), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0584.68077 |
| [14] | Wollmer, R., Removing arcs from a network, Oper. Res., 12, 934-940 (1965) · Zbl 0204.20102 |
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.
