{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T04:42:54Z","timestamp":1771476174936,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,7,10]],"date-time":"2007-07-10T00:00:00Z","timestamp":1184025600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"},{"start":{"date-parts":[[2007,7,10]],"date-time":"2007-07-10T00:00:00Z","timestamp":1184025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s00224-007-9025-6","type":"journal-article","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T23:13:27Z","timestamp":1184627607000},"page":"204-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":77,"title":["On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction"],"prefix":"10.1007","volume":"43","author":[{"given":"Leonid","family":"Khachiyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Endre","family":"Boros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konrad","family":"Borys","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabor","family":"Rudolf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jihui","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,10]]},"reference":[{"key":"9025_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":"9025_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. Oper. Res. Lett. 8, 73\u201376 (1989)","journal-title":"Oper. Res. Lett."},{"key":"9025_CR3","unstructured":"Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, University of Maryland, Institute of Advanced Computer Studies, College Park, MD (1995)"},{"key":"9025_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 http:\/\/www.it.uu.se\/research\/reports\/#2001)"},{"key":"9025_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 http:\/\/www.it.uu.se\/research\/reports\/#2001)"},{"issue":"2","key":"9025_CR6","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155(2), 210\u2013229 (2007)","journal-title":"Discret. Appl. Math."},{"key":"9025_CR7","doi-asserted-by":"crossref","unstructured":"Clementi, A.E.F., Crescenzi, P., Rossi, G.: On the complexity of approximating colored-graph problems. In: COCOON, pp. 281\u2013290 (1999)","DOI":"10.1007\/3-540-48686-0_28"},{"key":"9025_CR8","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. Oper. Res. Lett. 1, 157\u2013160 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9025_CR9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"9025_CR10","first-page":"A-334","volume":"20","author":"A. Ehrenfeucht","year":"1973","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional games over a graph. Not. Am. Math. Soc. 20, A-334 (1973)","journal-title":"Not. Am. Math. Soc."},{"key":"9025_CR11","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. Int. J. Game Theory 8, 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"issue":"3","key":"9025_CR12","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. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9025_CR13","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. Math. Program. 13, 116\u2013118 (1977)","journal-title":"Math. Program."},{"key":"9025_CR14","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 Math. Acad. Sci. Hung. 9, 395\u2013434 (1958)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9025_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9025_CR16","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. Nav. Res. Logist. Q. 18, 37\u201345 (1971)","journal-title":"Nav. Res. Logist. Q."},{"key":"9025_CR17","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. Nav. Res. Logist. Q. 25, 711\u2013713 (1978)","journal-title":"Nav. Res. Logist. Q."},{"issue":"2","key":"9025_CR18","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 9(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"key":"9025_CR19","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":"9025_CR20","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 Comput. Math. Math. Phys. 28, 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"9025_CR21","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. In: STOC \u201997: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 1\u201310. ACM Press (1997)","DOI":"10.1145\/258533.258536"},{"issue":"2","key":"9025_CR22","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 40(2), 97\u2013111 (2002)","journal-title":"Networks"},{"key":"9025_CR23","doi-asserted-by":"crossref","unstructured":"Jurdzinski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: SODA 2006, pp. 117\u2013123","DOI":"10.1145\/1109557.1109571"},{"key":"9025_CR24","doi-asserted-by":"crossref","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. In: ICALP, pp. 1043\u20131050 (2005)","DOI":"10.1007\/11523468_84"},{"key":"9025_CR25","doi-asserted-by":"crossref","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, New York (1972)"},{"key":"9025_CR26","doi-asserted-by":"crossref","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. Discret. Math. 23, 309\u2013311 (1978)","journal-title":"Discret. Math."},{"key":"9025_CR27","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. Math. Program. 60, 277\u2013293 (1993)","journal-title":"Math. Program."},{"key":"9025_CR28","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. Oper. Res. Lett. 8, 223\u2013227 (1989)","journal-title":"Oper. Res. Lett."},{"key":"9025_CR29","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. Nav. Res. Logist. Q. 17, 261\u2013268 (1970)","journal-title":"Nav. Res. Logist. Q."},{"key":"9025_CR30","unstructured":"Moulin, H.: Prolongement des jeux \u00e0 deux joueurs de somme nulle. Bull. Soc. Math. France, Memoire 45 (1976)"},{"issue":"2","key":"9025_CR31","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. J. Math. Anal. Appl. 55(2), 490\u2013507 (1976)","journal-title":"J. Math. Anal. Appl."},{"key":"9025_CR32","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":"9025_CR33","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. Math. Oper. Res. 24(4), 817\u2013828 (1999)","journal-title":"Math. Oper. Res."},{"key":"9025_CR34","first-page":"307","volume":"15","author":"S. Poljak","year":"1974","unstructured":"Poljak, S.: A note on the stable sets and coloring of graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"9025_CR35","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, New York (2003)"},{"key":"9025_CR36","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9025_CR37","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 20, 361\u2013371 (1990)","journal-title":"Networks"},{"issue":"2","key":"9025_CR38","doi-asserted-by":"crossref","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. Oper. Res. 43(2), 243\u2013251 (1995)","journal-title":"Oper. Res."},{"key":"9025_CR39","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. Math. Comput. Model. 17, 1\u201318 (1993)","journal-title":"Math. Comput. Model."},{"issue":"1\u20132","key":"9025_CR40","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. Theor. Comput. Sci. 158(1\u20132), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9025-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-007-9025-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9025-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9025-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T18:42:28Z","timestamp":1630435348000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-007-9025-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,10]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9025"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9025-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,10]]},"assertion":[{"value":"10 July 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}