{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:30Z","timestamp":1750306110510,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/13\/B\/ST6\/01811"],"award-info":[{"award-number":["2014\/13\/B\/ST6\/01811"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Focused Award on Algorithms for Large-scale Data Analysis"],"award-info":[{"award-number":["Focused Award on Algorithms for Large-scale Data Analysis"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["AMANDA"],"award-info":[{"award-number":["AMANDA"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010664","name":"H2020 Future and Emerging Technologies","doi-asserted-by":"publisher","award":["317532"],"award-info":[{"award-number":["317532"]}],"id":[{"id":"10.13039\/100010664","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055480","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"1108-1121","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Decremental single-source reachability in planar digraphs"],"prefix":"10.1145","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[{"name":"University of Rome Tor Vergata, Italy"}]},{"given":"Adam","family":"Karczmarz","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}]},{"given":"Jakub","family":"\u0141\u0105cki","sequence":"additional","affiliation":[{"name":"Google Research, USA"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914140"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684068"},{"key":"e_1_3_2_2_6_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Chechik Shiri","year":"1900","unstructured":"Shiri Chechik , Thomas Dueholm Hansen , Giuseppe F. Italiano , Veronika Loitzenbauer , and Nikos Parotsidis . Faster algorithms for computing maximal 2connected subgraphs in sparse directed graphs . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1900 \u20131918, 2017. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2connected subgraphs in sparse directed graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1900\u20131918, 2017."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.42"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118738.3118851"},{"key":"e_1_3_2_2_10_1","series-title":"Graduate texts in mathematics","volume-title":"Graph Theory","author":"Diestel Reinhard","year":"2012","unstructured":"Reinhard Diestel . Graph Theory , 4 th Edition, volume 173 of Graduate texts in mathematics . Springer , 2012 . Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.","edition":"4"},{"key":"e_1_3_2_2_11_1","first-page":"604","volume-title":"15th Annual European Symposium, Eilat, Israel, October 8-10, 2007","author":"Diks Krzysztof","year":"2007","unstructured":"Krzysztof Diks and Piotr Sankowski . Dynamic plane transitive closure. In Algorithms - ESA 2007 , 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007 , Proceedings , pages 594\u2013 604 , 2007 . Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 594\u2013604, 2007."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0002"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90004-V"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_2_16_1","volume-title":"Improved bounds for shortest paths in dense distance graphs. CoRR, abs\/1602.07013","author":"Gawrychowski Pawel","year":"2016","unstructured":"Pawel Gawrychowski and Adam Karczmarz . Improved bounds for shortest paths in dense distance graphs. CoRR, abs\/1602.07013 , 2016 . Pawel Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance graphs. CoRR, abs\/1602.07013, 2016."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955676"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00291-0"},{"key":"e_1_3_2_2_20_1","first-page":"724","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I","author":"Henzinger Monika","year":"2015","unstructured":"Monika Henzinger , Sebastian Krinninger , and Veronika Loitzenbauer . Finding 2edge and 2-vertex strongly connected components in quadratic time. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I , pages 713\u2013 724 , 2015 . Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer. Finding 2edge and 2-vertex strongly connected components in quadratic time. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 713\u2013724, 2015."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591869"},{"key":"e_1_3_2_2_22_1","first-page":"736","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I","author":"Henzinger Monika","year":"2015","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . Improved algorithms for decremental single-source reachability on directed graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I , pages 725\u2013 736 , 2015 . Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 725\u2013736, 2015."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280036"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_2_25_1","volume-title":"Patras, Greece","author":"Holm Jacob","year":"2015","unstructured":"Jacob Holm , Eva Rotenberg , and Christian Wulff-Nilsen . Faster fully-dynamic minimum spanning forest. In Algorithms - ESA 2015 - 23rd Annual European Symposium , Patras, Greece , Sept. 14-16, 2015 , Proceedings, pages 742\u2013753 , 2015. Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, Sept. 14-16, 2015, Proceedings, pages 742\u2013753, 2015."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222032"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095147"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627898"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_3_2_2_31_1","first-page":"155","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Klein Philip N.","year":"2005","unstructured":"Philip N. Klein . Multiple-source shortest paths in planar graphs . In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005 , Vancouver, BC, Canada , January 23-25, 2005 , pages 146\u2013 155 , 2005. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, BC, Canada, January 23-25, 2005, pages 146\u2013155, 2005."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483707"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.66"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746615"},{"key":"e_1_3_2_2_36_1","first-page":"166","volume-title":"Saarbr\u00fccken","author":"\u0141\u0105cki Jakub","year":"2011","unstructured":"Jakub \u0141\u0105cki and Piotr Sankowski . Min-cuts and shortest cycles in planar graphs in O (n log log n) time. In Algorithms - ESA 2011 - 19th Annual European Symposium , Saarbr\u00fccken , Germany , September 5-9, 2011 . Proceedings, pages 155\u2013 166 , 2011. Jakub \u0141\u0105cki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O (n log log n) time. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbr\u00fccken, Germany, September 5-9, 2011. Proceedings, pages 155\u2013166, 2011."},{"key":"e_1_3_2_2_37_1","volume-title":"32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015","author":"\u0141\u0105cki Jakub","year":"2015","unstructured":"Jakub \u0141\u0105cki and Piotr Sankowski . Optimal decremental connectivity in planar graphs . In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 , March 4-7, 2015 , Garching, Germany, pages 608\u2013621 , 2015. Jakub \u0141\u0105cki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 608\u2013621, 2015."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095135"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_2_42_1","first-page":"383","volume-title":"First Annual European Symposium","author":"Subramanian Sairam","year":"1993","unstructured":"Sairam Subramanian . A fully dynamic data structure for reachability in planar digraphs. In Algorithms - ESA \u201993 , First Annual European Symposium , Bad Honnef, Germany, September 30 - October 2, 1993 , Proceedings, pages 372\u2013 383 , 1993. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Algorithms - ESA \u201993, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 372\u2013383, 1993."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840401"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90164-O"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060607"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627943"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055480","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":49,"alternative-id":["10.1145\/3055399.3055480","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055480","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}