{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:29:23Z","timestamp":1781584163889,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384250","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1307-1316","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["An exponential time parameterized algorithm for planar disjoint paths"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"MPI-INF, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"IMSc, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"6th Workshop on Graph Classes, Optimization, and Width Parameters","author":"Adler Isolde","year":"2013","unstructured":"Isolde Adler . 2013 . 6th Workshop on Graph Classes, Optimization, and Width Parameters 2013, List of Open Problems. Isolde Adler. 2013. 6th Workshop on Graph Classes, Optimization, and Width Parameters 2013, List of Open Problems."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.10.001"},{"key":"e_1_3_2_1_3_1","unstructured":"Isolde Adler and Philipp Klaus Krause. 2010. A lower bound for the tree-width of planar graphs with vital linkages. CoRR abs\/1011.2136 ( 2010 ). arXiv: 1011.2136 http:\/\/arxiv.org\/abs\/1011.2136  Isolde Adler and Philipp Klaus Krause. 2010. A lower bound for the tree-width of planar graphs with vital linkages. CoRR abs\/1011.2136 ( 2010 ). arXiv: 1011.2136 http:\/\/arxiv.org\/abs\/1011.2136"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.12.010"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"e_1_3_2_1_7_1","volume-title":"APPROX\/RANDOM 2015","volume":"40","author":"Chuzhoy Julia","year":"2015","unstructured":"Julia Chuzhoy and David H. K. Kim . 2015. On Approximating Node-Disjoint Paths in Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2015 , August 24-26, 2015 , Princeton, NJ, USA (LIPIcs) , Vol. 40 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 187-211. Julia Chuzhoy and David H. K. Kim. 2015. On Approximating Node-Disjoint Paths in Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA (LIPIcs), Vol. 40. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 187-211."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897538"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055411"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188772"},{"key":"e_1_3_2_1_11_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"107","author":"Chuzhoy Julia","year":"2018","unstructured":"Julia Chuzhoy , David H. K. Kim , and Rachit Nimavat . 2018 . Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic (LIPIcs) , Vol. 107 . 38: 1-38 : 14. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. 2018. Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (LIPIcs), Vol. 107. 38: 1-38 : 14."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.29"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405009"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154833"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_3_2_1_19_1","unstructured":"Andr\u00e1s Frank. 1990. Packing paths cuts and circuits-a survey. Paths Flows and VLSI-Layout ( 1990 ) 49-100.  Andr\u00e1s Frank. 1990. Packing paths cuts and circuits-a survey. Paths Flows and VLSI-Layout ( 1990 ) 49-100."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.30"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Richard M Karp. 1975. On the computational complexity of combinatorial problems. Networks 5 1 ( 1975 ) 45-68.  Richard M Karp. 1975. On the computational complexity of combinatorial problems. Networks 5 1 ( 1975 ) 45-68.","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806784"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993697"},{"key":"e_1_3_2_1_26_1","first-page":"1812","volume-title":"Proceedings of the Twenty-Fifth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2014","author":"Philip","year":"2014","unstructured":"Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs . In Proceedings of the Twenty-Fifth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2014 , Portland, Oregon, USA , January 5-7, 2014 . SIAM, 1812 - 1830 . Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proceedings of the Twenty-Fifth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. SIAM, 1812-1830."},{"key":"e_1_3_2_1_27_1","unstructured":"Mark R Kramer and J van Leeuwen. 1984. The complexity of wirerouting and ifnding minimum area layouts for arbitrary VLSI circuits. Advances in computing research 2 ( 1984 ) 129-146.  Mark R Kramer and J van Leeuwen. 1984. The complexity of wirerouting and ifnding minimum area layouts for arbitrary VLSI circuits. Advances in computing research 2 ( 1984 ) 129-146."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41422-0_20"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061425.1061430"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322048"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_1_37_1","unstructured":"Petra Schefler. 1994. A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. TU Fachbereich 3.  Petra Schefler. 1994. A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. TU Fachbereich 3."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224061"},{"key":"e_1_3_2_1_39_1","volume-title":"Combinatorial optimization: polyhedra and eficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial optimization: polyhedra and eficiency . Vol. 24 . Springer Science & Business Media . Alexander Schrijver. 2003. Combinatorial optimization: polyhedra and eficiency. Vol. 24. Springer Science & Business Media."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384250","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":39,"alternative-id":["10.1145\/3357713.3384250","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384250","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}