{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:45:00Z","timestamp":1794339900576,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540341666","type":"print"},{"value":"9783540341680","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11753728_24","type":"book-chapter","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T16:17:13Z","timestamp":1146154633000},"page":"221-234","source":"Crossref","is-referenced-by-count":15,"title":["Extending Dijkstra\u2019s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Khachiyan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jihui","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"24_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey (1993)"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-6377(89)90003-5","volume":"8","author":"M.O. Ball","year":"1989","unstructured":"Ball, M.O., Golden, B.L., Vohra, R.V.: Finding the most vital arcs in a network. Operations Research Letters\u00a08, 73\u201376 (1989)","journal-title":"Operations Research Letters"},{"key":"24_CR3","unstructured":"Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes, University of Maryland, Institute of Anvanced Computer Studies, College Park, MD, Technical Report CS-TR-3539 (1995)"},{"key":"24_CR4","unstructured":"Beffara, E., Vorobyov, S.: Adapting Gurvich-Karzanov-Khachiyan\u2019s algorithm for parity games: Implementation and experimentation, Technical Report 020, Department of Information Technology, Uppsala University (2001), Available at: https:\/\/www.it.uu.se\/research\/reports\/#2001"},{"key":"24_CR5","unstructured":"Beffara, E., Vorobyov, S.: Is randomized Gurvich-Karzanov-Khachiyan\u2019s algorithm for parity games polynomial? Technical Report 025, Department of Information Technology, Uppsala University (2001), Available at: https:\/\/www.it.uu.se\/research\/reports\/#2001"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A Combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, DIMACS Technical Report 2004-05 (2004), Available at: http:\/\/dimacs.rutgers.edu\/TechnicalReports\/2004.html","DOI":"10.1007\/978-3-540-28629-5_52"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0167-6377(82)90020-7","volume":"1","author":"H.W. Corely","year":"1982","unstructured":"Corely, H.W., Shaw, D.Y.: Most vital links and nodes in weighted networks. Operations Research Letters\u00a01, 157\u2013160 (1982)","journal-title":"Operations Research Letters"},{"key":"24_CR8","unstructured":"Eherenfeucht, A., Mycielski, J.: Positional games over a graph. Notices of the American Mathematical Society\u00a020, A-334 (1973)"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A. Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journal of Game Theory\u00a08, 109\u2013113 (1979)","journal-title":"International Journal of Game Theory"},{"issue":"3","key":"24_CR10","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM\u00a034(3), 596\u2013615 (1987)","journal-title":"Journal of the ACM"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01584329","volume":"13","author":"D.R. Fulkerson","year":"1977","unstructured":"Fulkerson, D.R., Harding, G.C.: Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming\u00a013, 116\u2013118 (1977)","journal-title":"Mathematical Programming"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF02020271","volume":"9","author":"T. Gallai","year":"1958","unstructured":"Gallai, T.: Maximum-minimum S\u00e4tze \u00fcber Graphen. Acta Mathematica Academiae Scientiarum Hungaricae\u00a09, 395\u2013434 (1958)","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1002\/nav.3800180103","volume":"18","author":"P.M. Ghare","year":"1971","unstructured":"Ghare, P.M., Montgomery, D.C., Turner, T.M.: Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly\u00a018, 37\u201345 (1971)","journal-title":"Naval Research Logistics Quarterly"},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1002\/nav.3800250412","volume":"25","author":"B.L. Golden","year":"1978","unstructured":"Golden, B.L.: A problem in network interdiction. Naval Research Logistics Quarterly\u00a025, 711\u2013713 (1978)","journal-title":"Naval Research Logistics Quarterly"},{"issue":"2","key":"24_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problem are log space complete for P. SIGACT News\u00a09(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"key":"24_CR16","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V. Gurvich","year":"1988","unstructured":"Gurvich, V., Karzanov, A., Khachiyan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028, 85\u201391 (1988)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.10039","volume":"40","author":"E. Israely","year":"2002","unstructured":"Israely, E., Wood, K.: Shortest-path network interdiction. Networks\u00a040(2), 97\u2013111 (2002)","journal-title":"Networks"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R. Karp","year":"1978","unstructured":"Karp, R.: A Characterization of the Minimum Cycle Mean in a Digraph. Discrete Math.\u00a023, 309\u2013311 (1978)","journal-title":"Discrete Math."},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01580616","volume":"60","author":"A.V. Karzanov","year":"1993","unstructured":"Karzanov, A.V., Lebedev, V.N.: Cyclical games with prohibition. Mathematical Programming\u00a060, 277\u2013293 (1993)","journal-title":"Mathematical Programming"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","volume":"8","author":"K. Malik","year":"1989","unstructured":"Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Operations Research Letters\u00a08, 223\u2013227 (1989)","journal-title":"Operations Research Letters"},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/nav.3800170302","volume":"17","author":"A.W. McMasters","year":"1970","unstructured":"McMasters, A.W., Mustin, T.M.: Optimal interdiction of a supply networks. Naval Research Logistics Quarterly\u00a017, 261\u2013268 (1970)","journal-title":"Naval Research Logistics Quarterly"},{"key":"24_CR24","unstructured":"Moulin, H.: Prolongement des jeux \u00e0 deux joueurs de somme nulle. Bull. Soc. Math. France, Memoire\u00a045 (1976)"},{"issue":"2","key":"24_CR25","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-247X(76)90178-5","volume":"55","author":"H. Moulin","year":"1976","unstructured":"Moulin, H.: Extension of two person zero sum games. Journal of Mathematical Analysis and Apllication\u00a055(2), 490\u2013507 (1976)","journal-title":"Journal of Mathematical Analysis and Apllication"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Phillips, C.A.: The network inhibition problem. In: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pp. 776\u2013785 (1993)","DOI":"10.1145\/167088.167286"},{"issue":"4","key":"24_CR27","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1287\/moor.24.4.817","volume":"24","author":"N.N. Pisaruk","year":"1999","unstructured":"Pisaruk, N.N.: Mean cost cyclical games. Mathematics of Operations Research\u00a024(4), 817\u2013828 (1999)","journal-title":"Mathematics of Operations Research"},{"key":"24_CR28","volume-title":"Algorithms and Combinatorics","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. In: Algorithms and Combinatorics, vol.\u00a024, Springer, Heidelberg (2003)"},{"key":"24_CR29","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1002\/net.3230200402","volume":"20","author":"D.K. Wagner","year":"1990","unstructured":"Wagner, D.K.: Disjoint (s,t)-cuts in a network. Networks\u00a020, 361\u2013371 (1990)","journal-title":"Networks"},{"issue":"2","key":"24_CR30","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1287\/opre.43.2.243","volume":"43","author":"A. Washburn","year":"1995","unstructured":"Washburn, A., Wood, K.: Two-person zero-sum games for network interdiction. Operations Research\u00a043(2), 243\u2013251 (1995)","journal-title":"Operations Research"},{"key":"24_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0895-7177(93)90236-R","volume":"17","author":"R.K. Wood","year":"1993","unstructured":"Wood, R.K.: Deterministic network interdiction. Mathematical and Computer Modelling\u00a017, 1\u201318 (1993)","journal-title":"Mathematical and Computer Modelling"},{"issue":"1-2","key":"24_CR32","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U. Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158(1-2), 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11753728_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,26]],"date-time":"2021-07-26T01:13:29Z","timestamp":1627262009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11753728_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540341666","9783540341680"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/11753728_24","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11753728","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}