{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,21]],"date-time":"2022-06-21T19:11:21Z","timestamp":1655838681331},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1989,6,1]],"date-time":"1989-06-01T00:00:00Z","timestamp":612662400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1989,6]]},"DOI":"10.1007\/bf01553903","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T22:07:35Z","timestamp":1114034855000},"page":"471-501","source":"Crossref","is-referenced-by-count":7,"title":["Algorithms for multicommodity flows in planar graphs"],"prefix":"10.1007","volume":"4","author":[{"given":"Hitoshi","family":"Suzuki","sequence":"first","affiliation":[]},{"given":"Takao","family":"Nishizeki","sequence":"additional","affiliation":[]},{"given":"Nobuji","family":"Saito","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01553903_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01553903_CR2","series-title":"CORE Discussion Paper No.","volume-title":"Multicommodity maximum flow in planar networks (theD-algorithm approach)","author":"H. Diaz","year":"1972","unstructured":"H. Diaz and G. de Ghellinck, Multicommodity maximum flow in planar networks (theD-algorithm approach), CORE Discussion Paper No. 7212, Center for Operations Research and Econometrics, Louvain-la-Neuve, 1972."},{"key":"BF01553903_CR3","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson, Shortest-path problems in planar graphs,Proc. 24th IEEE Symp. on Foundations of Computer Science, Tucson, 1983, pp. 242\u2013247.","DOI":"10.1109\/SFCS.1983.69"},{"key":"BF01553903_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. Gabow","year":"1985","unstructured":"H. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union,J. Comput. System Sci.,30 (1985), pp. 209\u2013221.","journal-title":"J. Comput. System Sci."},{"key":"BF01553903_CR5","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1002\/net.3230140204","volume":"14","author":"R. Hassin","year":"1984","unstructured":"R. Hassin, On multicommodity flows in planar graphs,Networks,14 (1984), pp. 225\u2013235.","journal-title":"Networks"},{"issue":"2","key":"BF01553903_CR6","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton, D. J. Rose, and R. E. Tarjan, Generalized nested dissection,SIAM J. Numer. Anal,16, 2 (1979), pp. 346\u2013358.","journal-title":"SIAM J. Numer. Anal"},{"issue":"2","key":"BF01553903_CR7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/0214023","volume":"14","author":"K. Matsumoto","year":"1985","unstructured":"K. Matsumoto, T. Nishizeki, and N. Saito, An efficient algorithm for finding multicommodity flows in planar networks,SIAM J. Comput.,14, 2 (1985), pp. 289\u2013302.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"BF01553903_CR8","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1137\/0215034","volume":"15","author":"K. Matsumoto","year":"1985","unstructured":"K. Matsumoto, T. Nishizeki, and N. Saito, Planar multicommodity flows, maximum matchings, and negative cycles,SIAM J. Comput.,15, 2 (1985), pp. 495\u2013510.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"BF01553903_CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/TCAD.1985.1270099","volume":"4","author":"T. Nishizeki","year":"1985","unstructured":"T. Nishizeki, N. Saito, and K. Suzuki, A linear-time routing algorithm for convex grids,IEEE Trans. Computer-Aided Design,4, 1 (1985), pp. 68\u201376.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"BF01553903_CR10","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0166-218X(83)90100-2","volume":"6","author":"H. Okamura","year":"1983","unstructured":"H. Okamura, Multicommodity flows in graphs,Discrete Appl. Math.,6 (1983), pp. 55\u201362.","journal-title":"Discrete Appl. Math."},{"key":"BF01553903_CR11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H. Okamura","year":"1981","unstructured":"H. Okamura and P. D. Seymour, Multicommodity flows in planar graphs,J. Combin. Theory Ser. B,31 (1981), pp. 75\u201381.","journal-title":"J. Combin. Theory Ser. B"},{"key":"BF01553903_CR12","volume-title":"Doctoral Thesis","author":"M. Sakarovitch","year":"1966","unstructured":"M. Sakarovitch, The Multicommodity Flow Problem, Doctoral Thesis, Operations Research Center, University of California, Berkeley, 1966."},{"key":"BF01553903_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01584644","volume":"4","author":"M. Sakarovitch","year":"1973","unstructured":"M. Sakarovitch, Two commodity network flows and linear programming,Math. Programming,4 (1973), pp. 1\u201320.","journal-title":"Math. Programming"},{"key":"BF01553903_CR14","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees,J. Comput. System Sci.,26 (1983), pp. 362\u2013390.","journal-title":"J. Comput. System Sci."},{"key":"BF01553903_CR15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"J. W. Suurballe","year":"1984","unstructured":"J. W. Suurballe and R. E. Tarjan, A quick method for finding shortest pairs of disjoint paths,Networks,14 (1984), pp. 325\u2013336.","journal-title":"Networks"},{"key":"BF01553903_CR16","unstructured":"H. Suzuki, A. Ishiguro, and T. Nishizeki, Edge-disjoint paths in a region bounded by nested rectangles, Technical Report AL85-28, Institute of Electrical and Communication Engineers of Japan, 1985, pp. 13\u201322 (in Japanese)."},{"key":"BF01553903_CR17","doi-asserted-by":"crossref","unstructured":"H. Suzuki, T. Nishizeki, and N. Saito, Multicommodity flows in planar undirected graphs and shortest paths,Proc. 17th Annual ACM Symp. on Theory of Computing, 1985, pp. 195\u2013204.","DOI":"10.1145\/22145.22167"},{"key":"BF01553903_CR18","unstructured":"H. Suzuki, T. Nishizeki, and N. Saito, A variable priority queue and its applications, Technical Report CAS86-131, Institute of Electrical and Communication Engineers of Japan, 1986, pp. 23\u201333."},{"key":"BF01553903_CR19","unstructured":"\u00c9. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Report 84360-OR, Institut \u00d6konometrie und Operations Research, Rheinishe Friedrich-Wilhelms Universit\u00e4t, Bonn."},{"key":"BF01553903_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553903.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01553903\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T14:21:13Z","timestamp":1556893273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01553903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,6]]},"references-count":20,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1989,6]]}},"alternative-id":["BF01553903"],"URL":"https:\/\/doi.org\/10.1007\/bf01553903","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,6]]}}}