{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:14:26Z","timestamp":1743138866613,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-30448-4_7","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"82-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["How Vulnerable is an\u00a0Undirected Planar Graph with\u00a0Respect to\u00a0Max Flow"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6191-9801","authenticated-orcid":false,"given":"Lorenzo","family":"Balzotti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5464-4069","authenticated-orcid":false,"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows (1988)","DOI":"10.21236\/ADA594171"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B., Reddy, M.: Applications of network optimization. In: Handbooks in Operations Research and Management Science, vol. 7, pp. 1\u201383 (1995)","DOI":"10.1016\/S0927-0507(05)80118-5"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.5711\/1082598318121","volume":"18","author":"DL Alderson","year":"2013","unstructured":"Alderson, D.L., Brown, G.G., Carlyle, W.M., Cox, L.A., Jr.: Sometimes there is no \u201cmost-vital\u2019\u2019 arc: assessing and improving the operational resilience of systems. Mil. Oper. Res. 18, 21\u201337 (2013)","journal-title":"Mil. Oper. Res."},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.orl.2009.09.013","volume":"38","author":"DS Altner","year":"2010","unstructured":"Altner, D.S., Ergun, \u00d6., Uhan, N.A.: The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability. Oper. Res. Lett. 38, 33\u201338 (2010)","journal-title":"Oper. Res. Lett."},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1002\/net.21878","volume":"74","author":"G Ausiello","year":"2019","unstructured":"Ausiello, G., Franciosa, P.G., Lari, I., Ribichini, A.: Max flow vitality in general and st-planar graphs. Networks 74, 70\u201378 (2019)","journal-title":"Networks"},{"key":"7_CR6","unstructured":"Ausiello, G., Franciosa, P.G., Lari, I., Ribichini, A.: Max-flow vitality in undirected unweighted planar graphs. CoRR, abs\/2011.02375 (2020)"},{"key":"7_CR7","unstructured":"Balzotti, L., Franciosa, P.G.: Computing lengths of non-crossing shortest paths in planar graphs. CoRR, abs\/2011.04047 (2020)"},{"key":"7_CR8","unstructured":"Balzotti, L., Franciosa, P.G.: Max flow vitality of edges and vertices in undirected planar graphs. CoRR, abs\/2201.13099 (2022)"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"589","DOI":"10.7155\/jgaa.00610","volume":"26","author":"L Balzotti","year":"2022","unstructured":"Balzotti, L., Franciosa, P.G.: Non-crossing shortest paths in undirected unweighted planar graphs in linear time. J. Graph Algorithms Appl. 26, 589\u2013606 (2022)","journal-title":"J. Graph Algorithms Appl."},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-031-09574-0_6","volume-title":"Computer Science - Theory and Applications","author":"L Balzotti","year":"2022","unstructured":"Balzotti, L., Franciosa, P.G.: Non-crossing shortest paths in undirected unweighted planar graphs in linear time. In: Kulikov, A.S., Raskhodnikova, S. (eds.) CSR 2022. LNCS, vol. 13296, pp. 77\u201395. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-09574-0_6"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Balzotti, L., Franciosa, P.G.: Non-crossing shortest paths lengths in planar graphs in linear time. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, pp. xx\u2013yy. Springer, Cham (2023)","DOI":"10.2139\/ssrn.4404665"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N.: An $${O}(n \\log n)$$ algorithm for maximum st-flow in a directed planar graph. J. ACM 56, 9:1\u20139:30 (2009)","DOI":"10.1145\/1502793.1502798"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N.: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 735\u2013744. ACM (2013)","DOI":"10.1145\/2488608.2488702"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R Hassin","year":"1981","unstructured":"Hassin, R.: Maximum flow in (s, t) planar networks. Inf. Process. Lett. 13, 107 (1981)","journal-title":"Inf. Process. Lett."},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0208012","volume":"8","author":"A Itai","year":"1979","unstructured":"Itai, A., Shiloach, Y.: Maximum flow in planar networks. SIAM J. Comput. 8, 135\u2013150 (1979)","journal-title":"SIAM J. Comput."},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Italiano, G.F., Nussbaum, Y., Sankowski, P., Wulff-Nilsen, C.: Improved algorithms for min cut and max flow in undirected planar graphs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 313\u2013322. ACM (2011)","DOI":"10.1145\/1993636.1993679"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1006\/jagm.1994.1044","volume":"17","author":"V King","year":"1994","unstructured":"King, V., Rao, S., Tarjan, R.E.: A faster deterministic maximum flow algorithm. J. Algorithms 17, 447\u2013474 (1994)","journal-title":"J. Algorithms"},{"key":"7_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-31955-9_3","volume-title":"Network Analysis","author":"D Kosch\u00fctzki","year":"2005","unstructured":"Kosch\u00fctzki, D., Lehmann, K.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 16\u201361. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-31955-9_3"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 143\u2013148. ACM (2003)","DOI":"10.1145\/780542.780565"},{"key":"7_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-642-23719-5_14","volume-title":"Algorithms \u2013 ESA 2011","author":"J \u0141\u0105cki","year":"2011","unstructured":"\u0141\u0105cki, J., Sankowski, P.: Min-cuts and shortest cycles in planar graphs in $${O}({n} \\log \\log {n})$$ time. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 155\u2013166. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_14"},{"key":"7_CR24","first-page":"16","volume":"81","author":"L-G Mattsson","year":"2015","unstructured":"Mattsson, L.-G., Jenelius, E.: Vulnerability and resilience of transport systems\u2013a discussion of recent research. Transp. Res. Part A: Policy Pract. 81, 16\u201334 (2015)","journal-title":"Transp. Res. Part A: Policy Pract."},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10708-011-9412-z","volume":"78","author":"AT Murray","year":"2013","unstructured":"Murray, A.T.: An overview of network vulnerability modeling approaches. GeoJournal 78, 209\u2013221 (2013)","journal-title":"GeoJournal"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $${O}(nm)$$ time, or better. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 765\u2013774. ACM (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Phillips, C.A.: The network inhibition problem. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 776\u2013785. ACM (1993)","DOI":"10.1145\/167088.167286"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1287\/mnsc.21.5.531","volume":"21","author":"HD Ratliff","year":"1975","unstructured":"Ratliff, H.D., Sicilia, G.T., Lubore, S.: Finding the n most vital links in flow networks. Manag. Sci. 21, 531\u2013539 (1975)","journal-title":"Manag. Sci."},{"key":"7_CR29","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1137\/0212005","volume":"12","author":"JH Reif","year":"1983","unstructured":"Reif, J.H.: Minimum s-t cut of a planar undirected network in $${O}(n\\log ^2(n))$$ time. SIAM J. Comput. 12, 71\u201381 (1983)","journal-title":"SIAM J. Comput."},{"key":"7_CR30","unstructured":"Wollmer, R.D.: Some Methods for Determining the Most Vital Link in a Railway Network. Rand Corporation (1963)"},{"key":"7_CR31","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. Math. Comput. Model. 17, 1\u201318 (1993)","journal-title":"Math. Comput. Model."}],"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-031-30448-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:03:33Z","timestamp":1684191813000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}