{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:10:59Z","timestamp":1649178659490},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"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":[[1997,3]]},"DOI":"10.1007\/bf02523192","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:41:28Z","timestamp":1162960888000},"page":"266-280","source":"Crossref","is-referenced-by-count":8,"title":["Efficient parallel recognition of some circular arc graphs, II"],"prefix":"10.1007","volume":"17","author":[{"given":"L.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523192_CR1","doi-asserted-by":"crossref","unstructured":"D. Z. Chen and D. T. Lee. Solving the all-pair shortest path problem on interval and circular-arc graphs.Proceedings, International Parallel Processing Symposium, pp. 224\u2013228, 1994.","DOI":"10.1109\/IPPS.1994.288297"},{"key":"BF02523192_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/3-540-51542-9_25","volume-title":"Proceedings, Workshop on Algorithms and Data Structures","author":"L. Chen","year":"1989","unstructured":"L. Chen. NC algorithms for circular-arc graphs. In F. Dehne, J.-R. Sack, and N. Santoro, editors,Proceedings, Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 382, pp. 291\u2013302. Springer-Verlag, Berlin, 1989."},{"issue":"4","key":"BF02523192_CR3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(92)90239-R","volume":"42","author":"L. Chen","year":"1992","unstructured":"L. Chen. Optimal parallel time bounds for the maximum clique problem on intervals.Inform. Process. Lett., 42(4):197\u2013201, June 1992.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"BF02523192_CR4","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01190897","volume":"9","author":"L. Chen","year":"1993","unstructured":"L. Chen. Efficient parallel recognition of some circular arc graphs, I.Algorithmica, 9(3):217\u2013238, March 1993.","journal-title":"Algorithmica"},{"key":"BF02523192_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/3-540-58325-4_223","volume-title":"Proceedings, 5th Annual International Symposium on Algorithms and Computation","author":"L. Chen","year":"1994","unstructured":"L. Chen. Revisiting circular arc graphs. In D.-Z. Du and X.-S. Zhang, editors,Proceedings, 5th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 834, pp. 559\u2013566. Springer-Verlag, Berlin, 1994."},{"issue":"3","key":"BF02523192_CR6","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0196-6774(91)90010-V","volume":"12","author":"L. Chen","year":"1991","unstructured":"L. Chen and Y. Yesha. Parallel recognition of the consecutive ones property with applications.J. Algorithms, 12(3):375\u2013392, September 1991.","journal-title":"J. Algorithms"},{"issue":"1","key":"BF02523192_CR7","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1002\/net.3230230105","volume":"23","author":"L. Chen","year":"1993","unstructured":"L. Chen and Y. Yesha. Efficient parallel algorithms for bipartite permutation graphs.Networks, 23(1): 29\u201339, January 1993.","journal-title":"Networks"},{"key":"BF02523192_CR8","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs.Pacific. J. Math., 15: 835\u2013855, 1965.","journal-title":"Pacific. J. Math."},{"key":"BF02523192_CR9","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M. R. Garey","year":"1980","unstructured":"M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. The complexity of coloring circular arcs and chords.SIAM J. Algebraic Discrete Methods, 1:216\u2013227, 1980.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"BF02523192_CR10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0890-5401(87)90061-7","volume":"75","author":"X. He","year":"1987","unstructured":"X. He and Y. Yesha. Parallel recognition and decomposition of two terminal series parallel graphs.Inform. and Comput., 75:15\u201338, 1987.","journal-title":"Inform. and Comput."},{"key":"BF02523192_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/3-540-56279-6_98","volume-title":"Proceedings, Annual International Symposium on Algorithms and Computation","author":"W.-L. Hsu","year":"1992","unstructured":"W.-L. Hsu. A simple test for the consecutive ones property. In T. Ibaraki, Y. Inagaki, K. Iwama, T. Nishizeki, and M. Yamashita, editors,Proceedings, Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 650, pp. 459\u2013468. Springer-Verlag, Berlin, 1992."},{"key":"BF02523192_CR12","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, Vol. A, pp. 869\u2013941. North Holland, Amsterdam, 1990."},{"issue":"2","key":"BF02523192_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(84)90033-4","volume":"18","author":"C. C. Lee","year":"1984","unstructured":"C. C. Lee and D. T. Lee. On a circle-cover minimization problem.Inform. Process. Lett., 18(2): 109\u2013115, 1984.","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"BF02523192_CR14","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1137\/0219071","volume":"19","author":"D. T. Lee","year":"1990","unstructured":"D. T. Lee, M. Sarrafzadeh, and Y. F. Wu. Minimum cuts for circular-arc graphs.SIAM J. Comput., 19(6):1041\u20131050, December 1990.","journal-title":"SIAM J. Comput."},{"key":"BF02523192_CR15","doi-asserted-by":"crossref","unstructured":"M. V. Marathe, H. B. Hunt, III, and S. S. Ravi. Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs. In O. Abou-Rabia, C. K. Chang, and W. W. Koczkodaj, editors,Proceedings, 5th International Conference on Computing and Information, pp. 26\u201330, 1993.","DOI":"10.1109\/ICCI.1993.315408"},{"issue":"1","key":"BF02523192_CR16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0217003","volume":"17","author":"S. Masuda","year":"1988","unstructured":"S. Masuda and K. Nakajima. An optimal algorithm for finding a maximum independent set of a circular-arc graph.SIAM J. Comput., 17(1):41\u201352, 1988.","journal-title":"SIAM J. Comput."},{"key":"BF02523192_CR17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1137\/0602012","volume":"2","author":"J. B. Orlin","year":"1981","unstructured":"J. B. Orlin, M. A. Bonuccelli, and D. P. Bovet. AnO(n 2), algorithm for coloring proper circular arc graphs.SIAM J. Algebraic Discrete Methods, 2:88\u201393, 1981.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"6","key":"BF02523192_CR18","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1137\/0221061","volume":"21","author":"W.-K. Shih","year":"1992","unstructured":"W.-K. Shih, T. C. Chern, and W.-L. Hsu. AnO(n 2 logn) algorithm for the Hamiltonian cycle problem on circular-arc graphs.SIAM J. Comput., 21(6):1026\u20131046, December 1992.","journal-title":"SIAM J. Comput."},{"key":"BF02523192_CR19","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"J. Spinrad, A. Brandst\u00e4dt, and L. Stewart. Bipartite permutation graphs.Discrete Appl. Math., 18:279\u2013292, 1987.","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"BF02523192_CR20","doi-asserted-by":"crossref","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"A. C. Tucker","year":"1971","unstructured":"A. C. Tucker. Matrix characterization of circular-arc graphs.Pacific J. Math., 39(2):535\u2013545, 1971.","journal-title":"Pacific J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523192.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523192\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:39:41Z","timestamp":1558298381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02523192"],"URL":"https:\/\/doi.org\/10.1007\/bf02523192","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}