{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:14:40Z","timestamp":1672290880538},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,7]]},"abstract":"\n By a\n switch graph<\/jats:italic>\n , we mean an undirected graph\n G<\/jats:italic>\n = (\n P<\/jats:italic>\n \u228d\n W<\/jats:italic>\n ,\n E<\/jats:italic>\n ) such that all vertices in\n P<\/jats:italic>\n (the\n plugs<\/jats:italic>\n ) have degree one and all vertices in\n W<\/jats:italic>\n (the\n switches<\/jats:italic>\n ) have even degrees. We call\n G<\/jats:italic>\n plane<\/jats:italic>\n if\n G<\/jats:italic>\n is planar and can be embedded such that all plugs are in the outer face. Given a set (\n s<\/jats:italic>\n 1<\/jats:sub>\n ,\n t<\/jats:italic>\n 1<\/jats:sub>\n ), \u2026,(\n s<\/jats:italic>\n k<\/jats:sub>\n ,\n t<\/jats:italic>\n \n k<\/jats:italic>\n <\/jats:sub>\n ) of pairs of plugs, the problem is to find edge-disjoint paths\n p<\/jats:italic>\n 1<\/jats:sub>\n , \u2026,\n p<\/jats:italic>\n \n k<\/jats:italic>\n <\/jats:sub>\n such that every\n p<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n connects\n s<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n with\n t<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n . The best asymptotic worst-case complexity known so far is quadratic in the number of vertices. In this article, a linear, and thus asymptotically optimal, algorithm is introduced. This result may be viewed as a concluding \"keystone\" for a number of previous results on various special cases of the problem.\n <\/jats:p>","DOI":"10.1145\/1008731.1008737","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"636-670","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Edge-disjoint routing in plane switch graphs in linear time"],"prefix":"10.1145","volume":"51","author":[{"given":"Jan M.","family":"Hochstein","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}]},{"given":"Karsten","family":"Weihe","sequence":"additional","affiliation":[{"name":"University of Newcastle, Callaghan, NSW, Australia"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289496"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02579432","article-title":"Disjoint paths in a rectilinear grid","volume":"2","author":"Frank A.","year":"1982","unstructured":"Frank , A. 1982 . Disjoint paths in a rectilinear grid . Combinatorica 2 , 361 -- 371 . Frank, A. 1982. Disjoint paths in a rectilinear grid. Combinatorica 2, 361--371.","journal-title":"Combinatorica"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0095-8956(85)90046-2","article-title":"Edge-disjoint paths in planar graphs","volume":"39","author":"Frank A.","year":"1985","unstructured":"Frank , A. 1985 . Edge-disjoint paths in planar graphs . J. Comb. Theory B 39 , 164 -- 178 . Frank, A. 1985. Edge-disjoint paths in planar graphs. J. Comb. Theory B 39, 164--178.","journal-title":"J. Comb. Theory B"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1109\/43.46784","article-title":"A linear time algorithm for routing in a convex grid","volume":"9","author":"Kaufmann M.","year":"1990","unstructured":"Kaufmann , M. 1990 . A linear time algorithm for routing in a convex grid . IEEE Trans. CAD-ICAS 9 , 180 -- 184 . Kaufmann, M. 1990. A linear time algorithm for routing in a convex grid. IEEE Trans. CAD-ICAS 9, 180--184.","journal-title":"IEEE Trans. CAD-ICAS"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of ISA. Lecture Notes in Computer Science","volume":"557","author":"Kaufmann M.","unstructured":"Kaufmann , M. , and Kl\u00e4r , G . 1991. A faster algorithm for edge-disjoint paths in planar graphs . In Proceedings of ISA. Lecture Notes in Computer Science , vol. 557 . Springer-Verlag, New York, 336--348. Kaufmann, M., and Kl\u00e4r, G. 1991. A faster algorithm for edge-disjoint paths in planar graphs. In Proceedings of ISA. Lecture Notes in Computer Science, vol. 557. Springer-Verlag, New York, 336--348."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90016-7"},{"key":"e_1_2_1_7_1","unstructured":"Kaufmann M. and Mehlhorn K. 1990. Routing Problems in Grid Graphs. Springer-Verlag New York 165--184. Kaufmann M. and Mehlhorn K. 1990. Routing Problems in Grid Graphs. Springer-Verlag New York 165--184."},{"key":"e_1_2_1_8_1","volume-title":"Sorting and Searching, 2nd","author":"Knuth D.","unstructured":"Knuth , D. 1975. Art of Computer Programming , Vol. 3 : Sorting and Searching, 2nd Printing Addison-Wesley , Reading, Mass ., 168--177. Knuth, D. 1975. Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd Printing Addison-Wesley, Reading, Mass., 168--177."},{"key":"e_1_2_1_9_1","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","unstructured":"Lengauer , T. 1990. Combinatorial Algorithms for Integrated Circuit Layout . Wiley , New York . Lengauer, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4994"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01202792","article-title":"On the complexity of the disjoint path problem","volume":"13","author":"Middendorff M.","year":"1993","unstructured":"Middendorff , M. , and Pfeiffer , F. 1993 . On the complexity of the disjoint path problem . Combinatorica 13 , 97 -- 107 . Middendorff, M., and Pfeiffer, F. 1993. On the complexity of the disjoint path problem. Combinatorica 13, 97--107.","journal-title":"Combinatorica"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"M\u00f6hring R. and Wagner D. 1997. Combinatorial topics in VLSI design (annotated bibliography). Wiley New York 429--444. M\u00f6hring R. and Wagner D. 1997. Combinatorial topics in VLSI design (annotated bibliography). Wiley New York 429--444.","DOI":"10.1515\/9781400865338-013"},{"key":"e_1_2_1_13_1","unstructured":"Nishizeki T. and Chiba N. 1988. Planar graphs: Theory and algorithms. Ann. Disc. Math. 32. Nishizeki T. and Chiba N. 1988. Planar graphs: Theory and algorithms. Ann. Disc. Math. 32."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","article-title":"Multicommodity flows in planar graphs","volume":"31","author":"Okamura H.","year":"1981","unstructured":"Okamura , H. , and Seymour , P. 1981 . Multicommodity flows in planar graphs . J. Comb. Theory B 31 , 75 -- 81 . Okamura, H., and Seymour, P. 1981. Multicommodity flows in planar graphs. J. Comb. Theory B 31, 75--81.","journal-title":"J. Comb. Theory B"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ripphausen-Lipa H. Wagner D. and Weihe K. 1995. Efficient algorithms for disjoint paths in planar graphs. Vol. 20. American Mathematical Society Providence R I. 295--354. Ripphausen-Lipa H. Wagner D. and Weihe K. 1995. Efficient algorithms for disjoint paths in planar graphs. Vol. 20. American Mathematical Society Providence R I. 295--354.","DOI":"10.1090\/dimacs\/020\/06"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF01294465","article-title":"A linear-time algorithm for edge-disjoint paths in planar graphs","volume":"15","author":"Wagner D.","year":"1995","unstructured":"Wagner , D. , and Weihe , K. 1995 . A linear-time algorithm for edge-disjoint paths in planar graphs . Combinatorica 15 , 135 -- 150 . Wagner, D., and Weihe, K. 1995. A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica 15, 135--150.","journal-title":"Combinatorica"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"Weihe K.","year":"1999","unstructured":"Weihe , K. 1999 . Edge-disjoint routing in plane switch graphs in linear time . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science ( New York, N.Y., Oct. 17--19). IEEE Computer Society Press, Silver Spring, Md, 330--339. IEEE Catalog Number 99CB37039. Weihe, K. 1999. Edge-disjoint routing in plane switch graphs in linear time. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (New York, N.Y., Oct. 17--19). IEEE Computer Society Press, Silver Spring, Md, 330--339. IEEE Catalog Number 99CB37039."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008731.1008737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:43:34Z","timestamp":1672242214000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008731.1008737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1008731.1008737"],"URL":"https:\/\/doi.org\/10.1145\/1008731.1008737","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}