{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T16:53:14Z","timestamp":1680454394059},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,8,3]],"date-time":"2010-08-03T00:00:00Z","timestamp":1280793600000},"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":[[2011,9]]},"DOI":"10.1007\/s00453-010-9436-7","type":"journal-article","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T12:43:00Z","timestamp":1280752980000},"page":"174-189","source":"Crossref","is-referenced-by-count":8,"title":["Maximum Flow in Directed Planar Graphs with Vertex Capacities"],"prefix":"10.1007","volume":"61","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,3]]},"reference":[{"key":"9436_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"key":"9436_CR2","first-page":"1","volume":"56","author":"G. Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P.: An O(nlog\u2009n) algorithm for maximum st-flow in a directed planar graph. J.\u00a0ACM 56, 1\u201330 (2009)","journal-title":"J.\u00a0ACM"},{"key":"9436_CR3","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/s004530010029","volume":"28","author":"U. Brandes","year":"2000","unstructured":"Brandes, U., Wagner, D.: A linear time algorithm for the arc disjoint Menger problem in planar directed graphs. Algorithmica 28, 16\u201336 (2000)","journal-title":"Algorithmica"},{"key":"9436_CR4","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"9436_CR5","doi-asserted-by":"crossref","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":"9436_CR6","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1137\/0214045","volume":"14","author":"R. Hassin","year":"1985","unstructured":"Hassin, R., Johnson, D.B.: An O(nlog\u20092 n) algorithm for maximum flow in undirected planar networks. SIAM J. Comput. 14, 612\u2013624 (1985)","journal-title":"SIAM J. Comput."},{"key":"9436_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramania, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9436_CR8","doi-asserted-by":"crossref","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":"9436_CR9","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/31846.31849","volume":"34","author":"D.B. Johnson","year":"1987","unstructured":"Johnson, D.B.: Parallel algorithms for minimum cuts and maximum flows in planar networks. J. ACM 34, 950\u2013967 (1987)","journal-title":"J. ACM"},{"key":"9436_CR10","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF01240733","volume":"11","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Naor, J.: Flow in planar graphs with vertex capacities. Algorithmica 11, 200\u2013225 (1994)","journal-title":"Algorithmica"},{"key":"9436_CR11","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0406038","volume":"63","author":"S. Khuller","year":"1993","unstructured":"Khuller, S., Naor, J., Klein, P.: The lattice structure of flow in planar graphs. SIAM J. Discrete Math. 63, 477\u2013490 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"9436_CR12","series-title":"Ann. Discrete Math.","volume-title":"Planar Graphs: Theory and Algorithms","author":"T. Nishizwki","year":"1988","unstructured":"Nishizwki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Ann. Discrete Math., vol.\u00a032. North-Holland, Amsterdam (1988)"},{"key":"9436_CR13","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539793253565","volume":"26","author":"H. Ripphausen-Lipa","year":"1997","unstructured":"Ripphausen-Lipa, H., Wagner, D., Weihe, K.: The vertex-disjoint Menger problem in planar graphs. SIAM J. Comput. 26, 331\u2013349 (1997)","journal-title":"SIAM J. Comput."},{"key":"9436_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":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9436_CR15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1006\/jagm.1996.0831","volume":"23","author":"K. Weihe","year":"1997","unstructured":"Weihe, K.: Edge-disjoint (s,t)-paths in undirected planar graphs in linear time. J. Algorithms 23, 121\u2013138 (1997)","journal-title":"J. Algorithms"},{"key":"9436_CR16","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1006\/jcss.1997.1538","volume":"55","author":"K. Weihe","year":"1997","unstructured":"Weihe, K.: Maximum (s,t)-flows in planar networks in O(|V|log\u2009|V|)-time. J. Comput. Syst. Sci. 55, 454\u2013476 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9436_CR17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.ipl.2006.06.001","volume":"100","author":"X. Zhang","year":"2006","unstructured":"Zhang, X., Liang, W., Jiang, H.: Flow equivalent trees in node-edge-capacitated undirected planar graphs. Inf. Process. Lett. 100, 100\u2013115 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9436_CR18","series-title":"LNCS","first-page":"577","volume-title":"COCOON 2008","author":"X. Zhang","year":"2008","unstructured":"Zhang, X., Liang, W., Chen, G.: Computing maximum flows in undirected planar networks with both edge and vertex capacities. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 577\u2013586. Springer, Heidelberg (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9436-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9436-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9436-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:06Z","timestamp":1559123106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9436-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,3]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9436"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9436-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,3]]}}}