{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:53:13Z","timestamp":1725677593662},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_10","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T12:25:56Z","timestamp":1335615956000},"page":"105-116","source":"Crossref","is-referenced-by-count":1,"title":["Computing Maximum Non-crossing Matching in Convex Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaomin","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry \u2014 Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry \u2014 Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"10_CR2","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Canad J. Math.\u00a017, 449\u2013467 (1965)","journal-title":"Canad J. Math."},{"issue":"1","key":"10_CR4","first-page":"99","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Theory of Computing Systems\u00a010(1), 99\u2013127 (1977)","journal-title":"Theory of Computing Systems"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S., Tarjan, R.: Network flow and testing graph connectivity. SIAM J. Comput.\u00a04, 507\u2013518 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M. Fredman","year":"1975","unstructured":"Fredman, M.: On computing the length of longest increasing subsequences. Discrete Mathematics\u00a011(1), 29\u201335 (1975)","journal-title":"Discrete Mathematics"},{"key":"10_CR7","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. Gabow","year":"1985","unstructured":"Gabow, H., Tarjan, R.: A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences\u00a030, 209\u2013221 (1985)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H. Gabow","year":"1976","unstructured":"Gabow, H.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. Journal of the ACM\u00a023, 221\u2013234 (1976)","journal-title":"Journal of the ACM"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F. Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in a convex bipartite graph. Naval Res. Logist. Quart.\u00a014, 313\u2013316 (1967)","journal-title":"Naval Res. Logist. Quart."},{"issue":"4","key":"10_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. on Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. on Comput."},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski Jr.","year":"1981","unstructured":"Lipski Jr., W., Preparata, F.P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica\u00a015(4), 329\u2013346 (1981)","journal-title":"Acta Informatica"},{"key":"10_CR12","unstructured":"Kajitami, Y., Takahashi, T.: The noncross matching and applications to the 3-side switch box routing in VLSI layout design. In: Proc. International Symposium on Circuits and Systems, pp. 776\u2013779 (1986)"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H. Kuhn","year":"1955","unstructured":"Kuhn, H.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly\u00a02, 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(95)00145-3","volume":"56","author":"Y. Liang","year":"1995","unstructured":"Liang, Y., Blum, N.: Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits. Information Processing Letters\u00a056, 215\u2013219 (1995)","journal-title":"Information Processing Letters"},{"issue":"2","key":"10_CR15","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0166-218X(93)90090-B","volume":"47","author":"F. Malucelli","year":"1993","unstructured":"Malucelli, F., Ottmann, T., Pretolani, D.: Efficient labelling algorithms for the maximum noncrossing matching problem. Discrete Applied Mathematics\u00a047(2), 175\u2013179 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.: An $O(\\sqrt{|V|} |E|)$ algorithm for finding maximum matching in general graphs. In: Proc. of the 21st Annual Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G. Steiner","year":"1996","unstructured":"Steiner, G., Yeomans, J.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Computers and Mathematics with Applications\u00a031(2), 91\u201396 (1996)","journal-title":"Computers and Mathematics with Applications"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0020-0190(85)90067-5","volume":"10","author":"P. Widmayer","year":"1985","unstructured":"Widmayer, P., Wong, C.: An optimal algorithm for the maximum alignment of terminals. Information Processing Letters\u00a010, 75\u201382 (1985)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:13:59Z","timestamp":1620126839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}