{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:55:25Z","timestamp":1757314525426,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18173-8_3","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"47-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"key":"3_CR1","unstructured":"Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes. Technical report, College Park, MD, USA (1995)"},{"issue":"11","key":"3_CR2","doi-asserted-by":"publisher","first-page":"2888","DOI":"10.1016\/j.cor.2012.02.023","volume":"39","author":"C Bazgan","year":"2012","unstructured":"Bazgan, C., Toubaline, S., Vanderpooten, D.: Efficient determination of the $$k$$ most vital edges for the minimum spanning tree problem. Computers and Operations Research 39(11), 2888\u20132898 (2012)","journal-title":"Computers and Operations Research"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/s10878-011-9449-4","volume":"26","author":"C Bazgan","year":"2013","unstructured":"Bazgan, C., Toubaline, S., Vanderpooten, D.: Critical edges\/nodes for the minimum spanning tree problem: complexity and approximation. Journal of Combinatorial Optimization 26(1), 178\u2013189 (2013)","journal-title":"Journal of Combinatorial Optimization"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","volume":"27","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. Journal of Discrete Algorithms 27, 54\u201365 (2014)","journal-title":"Journal of Discrete Algorithms"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-319-06686-8_9","volume-title":"Computer Science - Theory and Applications","author":"A Boral","year":"2014","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A Fast Branching Algorithm for Cluster Vertex Deletion. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.\u00c9., Vereshchagin, N.K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 111\u2013124. Springer, Heidelberg (2014)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-32589-2_32","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M Doucha","year":"2012","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348\u2013359. Springer, Heidelberg (2012)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"3","key":"3_CR8","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics 34(3), 541\u2013566 (2013)","journal-title":"European Journal of Combinatorics"},{"key":"3_CR9","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"3_CR10","unstructured":"Frederickson, G.N., Solis-Oba, R.: Increasing the weight of minimum spanning trees. In: Proc. 7th SODA, pp. 539\u2013546 (1996)"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01584329","volume":"13","author":"D Fulkerson","year":"1977","unstructured":"Fulkerson, D., Harding, G.C.: Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming 13, 116\u2013118 (1977)","journal-title":"Mathematical Programming"},{"key":"3_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)"},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-319-08783-2_15","volume-title":"Computing and Combinatorics","author":"J Guo","year":"2014","unstructured":"Guo, J., Shrestha, Y.R.: Parameterized Complexity of Edge Interdiction Problems. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 166\u2013178. Springer, Heidelberg (2014)"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.10039","volume":"40","author":"E Israeli","year":"2002","unstructured":"Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97\u2013111 (2002)","journal-title":"Networks"},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/s00224-007-9025-6","volume":"43","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K.M., Gurvich, V., Rudolf, G., Zhao, J.: On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems 43(2), 204\u2013233 (2008)","journal-title":"Theory of Computing Systems"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-32589-2_2","volume-title":"Mathematical Foundations of Computer Science 2012","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Niedermeier, R.: New Races in Parameterized Algorithmics. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 19\u201330. Springer, Heidelberg (2012)"},{"key":"3_CR18","first-page":"58","volume":"113","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S.: Recent developments in kernelization: A survey. Bulletin of the EATCS 113, 58\u201397 (2014)","journal-title":"Bulletin of the EATCS"},{"issue":"2\u20133","key":"3_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0166-218X(01)00189-5","volume":"113","author":"W Liang","year":"2001","unstructured":"Liang, W.: Finding the $$k$$ most vital edges with respect to minimum spanning trees for fixed $$k$$. Discrete Applied Mathematics 113(2\u20133), 319\u2013327 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR20","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., Gupta, S.K.: The $$k$$ most vital arcs in the shortest path problem. Operations Research Letters 8, 223\u2013227 (1989)","journal-title":"Operations Research Letters"},{"issue":"2","key":"3_CR21","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(00)00175-7","volume":"79","author":"E Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Information Processing Letters 79(2), 81\u201385 (2001)","journal-title":"Information Processing Letters"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"3_CR23","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proc. 27th STACS, vol. 5. LIPIcs, pp. 17\u201332. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2010)"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-40328-6_23","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"F Pan","year":"2013","unstructured":"Pan, F., Schild, A.: Interdiction Problems on Planar Graphs. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 317\u2013331. Springer, Heidelberg (2013)"},{"key":"3_CR25","unstructured":"Sorge, M., Weller, M.: The graph parameter hierarchy. Manuscript (2013). http:\/\/fpt.akt.tu-berlin.de\/msorge\/parameter-hierarchy.pdf"},{"issue":"2","key":"3_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0895-7177(93)90236-R","volume":"17","author":"RK Wood","year":"1993","unstructured":"Wood, R.K.: Deterministic network interdiction. Mathematical and Computer Modeling 17(2), 1\u201318 (1993)","journal-title":"Mathematical and Computer Modeling"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T16:21:40Z","timestamp":1674231700000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}