{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:03:46Z","timestamp":1725480226215},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405054"},{"type":"electronic","value":"9783540450665"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45066-1_13","type":"book-chapter","created":{"date-parts":[[2007,2,28]],"date-time":"2007-02-28T07:41:13Z","timestamp":1172648473000},"page":"168-180","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Algorithms for Disjoint Matchings among Intervals and Related Problems"],"prefix":"10.1007","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Gardi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"13_CR1","volume-title":"Graphs","author":"C. Berge","year":"1985","unstructured":"C. Berge (1985). Graphs. Elsevier Science Publishers B.V., Amsterdam, 2nd edition.","edition":"2nd edition"},{"key":"13_CR2","series-title":"Computer Science and Applied Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic (1980). Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics. Academic Press, New-York."},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0196-6774(84)90043-9","volume":"5","author":"P. Ramanan","year":"1984","unstructured":"P. Ramanan, J. Deogun, and C. Liu (1984). A personnel assignment problem. Journal of Algorithms 5, 132\u2013144.","journal-title":"Journal of Algorithms"},{"issue":"6","key":"13_CR4","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1287\/mnsc.39.6.728","volume":"39","author":"G. Steiner","year":"1993","unstructured":"G. Steiner and J.S. Yeomans (1993). Level schedules for mixed-model, just-in-time processes. Management Science 39(6), 728\u2013735.","journal-title":"Management Science"},{"key":"13_CR5","first-page":"125","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds (1965). Maximum matching and a polyedron with 0,1 vertices. Journal of Research of N.B.S. B 69, 125\u2013130.","journal-title":"Journal of Research of N.B.S. B"},{"key":"13_CR6","unstructured":"S. Micali and V.V. Vazirani (1980). An \n                    \n                      \n                    \n                    $$\nO(\\sqrt V E)\n$$\n                   algorithm for finding maximum matching in general graphs. In Proc. 21st Annual Symposium on Foundations of Computer Science, pages 17\u201327."},{"key":"13_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970401","volume-title":"Graph Theory and its Applications to Problems of Society","author":"F.S. Roberts","year":"1978","unstructured":"F.S. Roberts (1978). Graph Theory and its Applications to Problems of Society. SIAM, Philadelphia, PA."},{"key":"13_CR8","unstructured":"M.G. Andrews and D.T. Lee (1992). An optimal algorithm for matching in interval graphs. manuscript."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s004539910013","volume":"26","author":"M.G. Andrews","year":"2000","unstructured":"M.G. Andrews, M.J. Atallah, D.Z. Chen, and D.T. Lee (2000). Parallel algorithms for maximum matching in complements of interval graphs and related problems. Algorithmica 26, 263\u2013289.","journal-title":"Algorithmica"},{"key":"13_CR10","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e0j\u00e0","year":"1992","unstructured":"J. J\u00e0j\u00e0 (1992). An Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA."},{"key":"13_CR11","unstructured":"M.R. Garey and J.S. Johnson (1979). Computer and Intractability: A Guide to NP-Completeness. W.H. Freeman."},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"H.L. Bodlaender","year":"1995","unstructured":"H.L. Bodlaender and K. Jansen (1995). Restrictions of graph partition problems. Part I. Theoretical Computer Science 148, 93\u2013109.","journal-title":"Theoretical Computer Science"},{"key":"13_CR13","unstructured":"Bamboo-Planification by Prologia-Groupe Air Liquide. \n                    http:\/\/prologianet.univ-mrs.fr\/bamboo\/bamboo_planification.html"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"U.I. Gupta, D.T. Lee, and J.Y.-T. Leung (1982). Efficient algorithms for interval and circular-arc graphs. Networks 12, 459\u2013467.","journal-title":"Networks"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"S. Olariu","year":"1991","unstructured":"S. Olariu (1991). An optimal greedy heuristic to color interval graphs. Information Processing Letters 37, 21\u201325.","journal-title":"Information Processing Letters"},{"issue":"3","key":"13_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"4","author":"F. Glover","year":"1967","unstructured":"F. Glover (1967). Maximum matchings in a convex bipartite graph. Naval Research Logistics Quartely 4(3), 313\u2013316.","journal-title":"Naval Research Logistics Quartely"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski Jr.","year":"1981","unstructured":"W. Lipski, Jr. and F.P. Preparata (1981). Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15, 329\u2013346.","journal-title":"Acta Informatica"},{"issue":"1","key":"13_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0167-6377(84)90068-3","volume":"3","author":"G. Gallo","year":"1984","unstructured":"G. Gallo (1984). An O(n log n) algorithm for the convex bipartite matching problem. Operation Research Letters 3(1), 31\u201334.","journal-title":"Operation Research Letters"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"H.N. Gabow and R.E. Tarjan (1985). An linear-time algorithm for the special set union. Journal of Computer and System Sciences 30, 209\u2013221.","journal-title":"Journal of Computer and System Sciences"},{"issue":"12","key":"13_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G. Steiner","year":"1996","unstructured":"G. Steiner and J.S. Yeomans (1996). A linear time algorithm for maximum matchings in convex, bipartite graphs. Computers and Mathematics with Applications 31(12), 91\u201396.","journal-title":"Computers and Mathematics with Applications"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"S.A. Cook and R.A. Reckhow (1973). Time bounded random access machines. Journal of Computer and System Sciences 7, 354\u2013375.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"M. Habib, R. McConnel, C. Paul, and L. Viennot (2000). Lex-BSF and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science 234, 59\u201384.","journal-title":"Theoretical Computer Science"},{"key":"13_CR23","unstructured":"S.K. Kim (1989). Optimal parallel algorithms on sorted intervals. In Proc. 27th Annual Allerton Conference on Communication, Control and Computing, pages 766\u2013775. Monticello, IL."}],"container-title":["Lecture Notes in Computer Science","Discrete Mathematics and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45066-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T21:59:19Z","timestamp":1550267959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45066-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405054","9783540450665"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45066-1_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}