{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T23:55:16Z","timestamp":1778975716607,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642450297","type":"print"},{"value":"9783642450303","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_49","type":"book-chapter","created":{"date-parts":[[2013,12,12]],"date-time":"2013-12-12T02:32:52Z","timestamp":1386815572000},"page":"524-534","source":"Crossref","is-referenced-by-count":8,"title":["Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs"],"prefix":"10.1007","author":[{"given":"C. Gregory","family":"Plaxton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"49_CR1","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1073\/pnas.43.9.842","volume":"43","author":"C. Berge","year":"1957","unstructured":"Berge, C.: Two theorems in graph theory. Proceedings of the National Academy of Sciences\u00a043, 842\u2013844 (1957)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"49_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-540-74456-6_37","volume-title":"Mathematical Foundations of Computer Science 2007","author":"G.S. Brodal","year":"2007","unstructured":"Brodal, G.S., Georgiadis, L., Hansen, K.A., Katriel, I.: Dynamic matchings in convex bipartite graphs. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 406\u2013417. Springer, Heidelberg (2007)"},{"key":"49_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BFb0009490","volume-title":"Algorithms and Computation","author":"M.-S. Chang","year":"1996","unstructured":"Chang, M.-S.: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 146\u2013155. Springer, Heidelberg (1996)"},{"key":"49_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"49_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"Dekel, E., Sahni, S.: A parallel matching algorithm for convex bipartite graphs and applications to scheduling. Journal of Parallel and Distributed Computing\u00a01, 185\u2013205 (1984)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"49_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: 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":"49_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0167-6377(84)90068-3","volume":"3","author":"G. Gallo","year":"1984","unstructured":"Gallo, G.: An O(nlogn) algorithm for the convex bipartite matching problem. Operations Research Letters\u00a03, 31\u201334 (1984)","journal-title":"Operations Research Letters"},{"key":"49_CR8","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 convex bipartite graphs. Naval Research Logistic Quarterly\u00a014, 313\u2013316 (1967)","journal-title":"Naval Research Logistic Quarterly"},{"key":"49_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1287\/ijoc.1070.0232","volume":"20","author":"I. Katriel","year":"2008","unstructured":"Katriel, I.: Matchings in node-weighted convex bipartite graphs. INFORMS Journal on Computing\u00a020, 205\u2013211 (2008)","journal-title":"INFORMS Journal on Computing"},{"key":"49_CR10","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, 329\u2013346 (1981)","journal-title":"Acta Informatica"},{"key":"49_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM Journal on Computing\u00a014, 257\u2013276 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"49_CR12","doi-asserted-by":"publisher","first-page":"230","DOI":"10.4153\/CJM-1958-027-8","volume":"10","author":"N.S. Mendelsohn","year":"1958","unstructured":"Mendelsohn, N.S., Dulmage, A.L.: Some generalizations of the problem of distinct representatives. Canadian Journal of Mathematics\u00a010, 230\u2013241 (1958)","journal-title":"Canadian Journal of Mathematics"},{"key":"49_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-540-70575-8_19","volume-title":"Automata, Languages and Programming","author":"C.G. Plaxton","year":"2008","unstructured":"Plaxton, C.G.: Fast scheduling of weighted unit jobs with release times and deadlines. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 222\u2013233. Springer, Heidelberg (2008)"},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"Plaxton, C.G.: Vertex-weighted matching in two-directional orthogonal ray graphs. Technical Report TR\u201313\u201316, Department of Computer Science, University of Texas at Austin (September 2013)","DOI":"10.1007\/978-3-642-45030-3_49"},{"key":"49_CR15","first-page":"63","volume":"46","author":"M.G. Scutell\u00e0","year":"1988","unstructured":"Scutell\u00e0, M.G., Scevola, G.: A modification of Lipski-Preparata\u2019s algorithm for the maximum matching problem on bipartite convex graphs. Ricerca Operativa\u00a046, 63\u201377 (1988)","journal-title":"Ricerca Operativa"},{"key":"49_CR16","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1016\/j.dam.2010.06.002","volume":"158","author":"A.M.S. Shrestha","year":"2010","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: On orthogonal ray graphs. Discrete Applied Mathematics\u00a0158, 1650\u20131659 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"49_CR17","unstructured":"Soto, J.A.: Contributions on Secretary Problems, Independents Sets of Rectangles and Related Problems. PhD thesis, Department of Mathematics, Massachusetts Institute of Technology (June 2011)"},{"key":"49_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/3-540-13345-3_42","volume-title":"Automata, Languages, and Programming","author":"T.H. Spencer","year":"1984","unstructured":"Spencer, T.H., Mayr, E.W.: Node weighted matching. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol.\u00a0172, pp. 454\u2013464. Springer, Heidelberg (1984)"},{"key":"49_CR19","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.S.: A linear time algorithm for determining maximum matchings in convex, bipartite graphs. Computers and Mathematics with Applications\u00a031, 91\u201396 (1996)","journal-title":"Computers and Mathematics with Applications"},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. Journal of the ACM\u00a022, 215\u2013225 (1975)","journal-title":"Journal of the ACM"},{"key":"49_CR21","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T10:41:22Z","timestamp":1558780882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}