{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:52Z","timestamp":1725663292825},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_25","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:06:25Z","timestamp":1330203985000},"page":"291-302","source":"Crossref","is-referenced-by-count":2,"title":["NC algorithms for circular-arc graphs"],"prefix":"10.1007","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0166-218X(85)90025-3","volume":"12","author":"M. A. Bonuccelli","year":"1985","unstructured":"M.A. Bonuccelli, Dominating sets and domatic numbers of circular-arc graphs, Discrete Appl. Math. 12 (1985), 203\u2013213.","journal-title":"Discrete Appl. Math."},{"key":"25_CR2","unstructured":"L. Chen, Y. Yesha, \u201cEfficient parallel algorithms for recognizing transformable convex bipartite graphs and finding their maximum matchings\u201d, OSU-CISRC-8\/88-TR 26, The Ohio State University, 1988."},{"key":"25_CR3","unstructured":"L. Chen, Y. Yesha, \u201cParallel algorithms: testing for interval graphs and the circular ones property\u201d, OSU-CISRC-9\/88-TR 29, The Ohio State University, 1988."},{"key":"25_CR4","unstructured":"L. Chen, Y. Yesha, Fast parallel algorithms for bipartite permutation graphs, in \u201cProceedings 26th Ann. Allerton Conf. on Communication, Control, and Computing\u201d, University of Illinois at Urbana-Champaign, 1988."},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"L. Chen, Efficient parallel algorithms for several intersection graphs, in \u201cProceedings Int'l Symp. on Circuits and Systems\u201d, IEEE, 1989.","DOI":"10.1109\/ISCAS.1989.100514"},{"key":"25_CR6","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, C.H. Papadimitriou, The complexity of coloring circular arcs and chords, SIAM J. Algebraic and Discrete Methods 1 (1980), 216\u2013227.","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"F. Gavril","year":"1974","unstructured":"F. Gavril, Algorithms on circular-arc graphs, Networks 4 (1974), 357\u2013369.","journal-title":"Networks"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U. I. Gupta","year":"1982","unstructured":"U.I. Gupta, D.T. Lee, J.Y.-T. Leung, Efficient algorithms for interval graphs and circular-arc graphs, Networks 12 (1982), 459\u2013467.","journal-title":"Networks"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/0214018","volume":"14","author":"W.-L. Hsu","year":"1985","unstructured":"W.-L. Hsu, Maximum weight clique algorithms for circular-arc graphs and circle graphs, SIAM J. Comp. 14 (1985), 224\u2013231.","journal-title":"SIAM J. Comp."},{"key":"25_CR10","unstructured":"W.-L. Hsu, K. Tsai, Linear time algorithms on circular-arc graphs, in \u201cProceedings 26th Ann. Allerton Conf. on Communication, Control, and Computing\u201d, University of Illinois at Urbana-Champaign, 1988."},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.2044-8317.1974.tb00534.x","volume":"27","author":"L. Hubert","year":"1974","unstructured":"L. Hubert, Some applications of graph theory and related non-metric techniques to problems of approximate seriation: the case of symmetric proximity measures, British J. Math. Statist. Psych. 27 (1974), 133\u2013153.","journal-title":"British J. Math. Statist. Psych."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"P. Klein, Efficient parallel algorithms for chordal graphs, in \u201cProceedings 29th Ann. Symp. on Foundations of Computer Science\u201d, IEEE Computer Society, 1988.","DOI":"10.1109\/SFCS.1988.21933"},{"key":"25_CR13","first-page":"189","volume":"23","author":"R. D. Luce","year":"1971","unstructured":"R.D. Luce, Periodic extensive measurement, Compositio Math. 23 (1971), 189\u2013198.","journal-title":"Compositio Math."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0217003","volume":"17","author":"S. Masuda","year":"1988","unstructured":"S. Masuda, K. Nakajima, An optimal algorithm for finding a maximum independent set of a circulararc graph, SIAM J. Comput. 17 (1988), 41\u201352.","journal-title":"SIAM J. Comput."},{"key":"25_CR15","unstructured":"A. Moitra, R. Johnson, PT-optimal algorithms for interval graphs, in \u201cProceedings 26th Ann. Allerton Conf. on Communication, Control, and Computing\u201d, University of Illinois at Urbana-Champaign, 1988."},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"J. Naor, M. Naor, A.A. Schaeffer, Fast parallel algorithms for chordal graphs, in \u201cProceedings 19th Ann. ACM Symp. on Theory of Computing\u201d, pp. 355\u2013364, Association for Computing Machinery, 1987, and (a fuller version) IBM Research Report RJ5629, April 1987.","DOI":"10.1145\/28395.28433"},{"issue":"Suppl.1","key":"25_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jcp.1040700403","volume":"70","author":"F. W. Stahl","year":"1967","unstructured":"F.W. Stahl, Circular genetic maps, J. Cell. Physiol. 70 (Suppl. 1) (1967), 1\u201312.","journal-title":"J. Cell. Physiol."},{"key":"25_CR18","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0041-1647(68)90016-6","volume":"2","author":"K. E. Stouffers","year":"1968","unstructured":"K.E. Stouffers, Scheduling of traffic lights-a new approach, Transportation Res. 2 (1968), 199\u2013234.","journal-title":"Transportation Res."},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0012-365X(76)80011-8","volume":"16","author":"W. Trotter","year":"1976","unstructured":"W. Trotter, J. Moore, Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math. 16 (1976), 361\u2013381.","journal-title":"Discrete Math."},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.1090\/S0002-9904-1970-12628-3","volume":"76","author":"A. C. Tucker","year":"1970","unstructured":"A.C. Tucker, Characterizing circular-arc graphs, Bull. Amer. Math. Soc. 76 (1970), 1257\u20131260.","journal-title":"Bull. Amer. Math. Soc."},{"key":"25_CR21","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 characterizations of circular-arc graphs, Pacific J. Math. 39 (1971), 535\u2013545.","journal-title":"Pacific J. Math."},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. C. Tucker","year":"1975","unstructured":"A.C. Tucker, Coloring a family of circular-arc graphs, SIAM J. Appl. Math. 29 (1975), 493\u2013502.","journal-title":"SIAM J. Appl. Math."},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"A.C. Tucker, Circular-arc graphs: new uses and a new algorithm, in \u201cTheory and Application of Graphs\u201d, Lecture Notes in Math., Vol. 642, 580\u2013589, Springer-Verlag, 1978.","DOI":"10.1007\/BFb0070412"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. C. Tucker","year":"1980","unstructured":"A.C. Tucker, An efficient test for circular-arc graphs, SIAM J. Comput. 9 (1980), 1\u201324.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:54Z","timestamp":1605648114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}