{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:32Z","timestamp":1725516812564},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_57","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"577-586","source":"Crossref","is-referenced-by-count":2,"title":["Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities"],"prefix":"10.1007","author":[{"given":"Xianchao","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weifa","family":"Liang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoliang","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"57_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R.K. Ahujia","year":"1993","unstructured":"Ahujia, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, New Jersey (1993)"},{"key":"57_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Elsevier, North-Holland (1976)"},{"key":"57_CR3","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.: An O(nlogn) Algorithm for Maximum s-t Flow in a Directed Planar Graph. In: Proceedings of the 17th Annual ACM-SIAM Symopsimum on Discrete Algorithms (SODA 2006), pp. 524\u2013533 (2006)","DOI":"10.1145\/1109557.1109615"},{"key":"57_CR4","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A New Approach to the Maximum Flow Problem. Journal of the ACM\u00a035, 921\u2013940 (1988)","journal-title":"Journal of the ACM"},{"key":"57_CR5","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the Flow Decomposition Barrier. Journal of the ACM\u00a045, 783\u2013797 (1998)","journal-title":"Journal of the ACM"},{"key":"57_CR6","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic Sorting in O(nloglogn) Time and Linear Space. Journal of Algorithms\u00a050, 96\u2013105 (2004)","journal-title":"Journal of Algorithms"},{"key":"57_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R. Hassin","year":"1981","unstructured":"Hassin, R.: Maximum Flows in (s,t) Planar Networks. Information Processing Letters\u00a013, 107 (1981)","journal-title":"Information Processing Letters"},{"key":"57_CR8","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1137\/0214045","volume":"14","author":"R. Hassin","year":"1985","unstructured":"Hassin, R., Johnson, D.S.: An O(nlog2 n) Algorithm for Maximum Flow in Undirected Planar Networks. SIAM Journal on Computing\u00a014, 612\u2013624 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"57_CR9","volume-title":"Integer Programing and Network Flows","author":"T.C. Hu","year":"1969","unstructured":"Hu, T.C.: Integer Programing and Network Flows. Addison-Wesley, Reading (1969)"},{"key":"57_CR10","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/BF01240733","volume":"11","author":"S. Khuler","year":"1994","unstructured":"Khuler, S., Naor, J.: Flow in Planar Graphs with Vertex Capacities. Algoirthmica\u00a011, 200\u2013225 (1994)","journal-title":"Algoirthmica"},{"key":"57_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"P. Klein","year":"1997","unstructured":"Klein, P., Rao, S.B., Rauch-Henzinger, M., Subramanian, S.: Faster Shortest-Path Algorithms for Planar Graphs. Journal of Computer and System Science\u00a055, 3\u201323 (1997)","journal-title":"Journal of Computer and System Science"},{"key":"57_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1137\/0212005","volume":"12","author":"J.H. Reif","year":"1983","unstructured":"Reif, J.H.: Minimum s\u2009\u2212\u2009t Cut of a Planar Undirected Network in O(nlog2 n) Time. SIAM Journal on Computing\u00a012, 71\u201381 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"57_CR13","doi-asserted-by":"publisher","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 Tree. Journal of Computer and System Science\u00a026, 362\u2013391 (1983)","journal-title":"Journal of Computer and System Science"},{"key":"57_CR14","doi-asserted-by":"publisher","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-Capacitied Undirected Planar Graphs. Information Processing Letters\u00a0100, 100\u2013115 (2006)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:02:22Z","timestamp":1605744142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}