{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:37:04Z","timestamp":1773409024310,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,8,3]],"date-time":"2010-08-03T00:00:00Z","timestamp":1280793600000},"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":[[2011,11]]},"DOI":"10.1007\/s00453-010-9432-y","type":"journal-article","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T16:38:23Z","timestamp":1280767103000},"page":"694-737","source":"Crossref","is-referenced-by-count":7,"title":["A Simpler Linear-Time Recognition of Circular-Arc Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,3]]},"reference":[{"key":"9432_CR1","series-title":"London Mathematical Society Monographs","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. London Mathematical Society Monographs, vol.\u00a011. Academic Press, London (1978)"},{"issue":"3","key":"9432_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9432_CR3","unstructured":"Conitzer, V., Derryberry, J., Sandholm, T.: Combinatorial auctions with structured item graphs. In: Proceedings of the Nineteenth National Conference on Artificial Intelligence, pp. 212\u2013218 (2004)"},{"key":"9432_CR4","unstructured":"Eschen, E.M.: Circular-arc graph recognition and related problems. PhD thesis, Department of Computer Science, Vanderbilt University (1997)"},{"key":"9432_CR5","unstructured":"Eschen, E.M., Spinrad, J.P.: An O(n 2) algorithm for circular-arc graph recognition. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0128\u2013137 (1993)"},{"key":"9432_CR6","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357\u2013369 (1974)","journal-title":"Networks"},{"key":"9432_CR7","volume-title":"Combinatorial Geometry in the Plane","author":"H. Hadwiger","year":"1964","unstructured":"Hadwiger, H., Debrunner, H., Klee, V.: Combinatorial Geometry in the Plane. Holt, Rinehart & Winston, New York (1964)"},{"issue":"3","key":"9432_CR8","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539793260726","volume":"24","author":"W.-L. Hsu","year":"1995","unstructured":"Hsu, W.-L.: O(mn) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM J. Comput. 24(3), 411\u2013439 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9432_CR9","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0304-3975(02)00435-8","volume":"296","author":"W.-L. Hsu","year":"2003","unstructured":"Hsu, W.-L., McConnell, R.M.: PC-trees and circular-ones arrangements. Theor. Comput. Sci. 296(1), 99\u2013116 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9432_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/11785293_7","volume-title":"10th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"H. Kaplan","year":"2006","unstructured":"Kaplan, H., Nussbaum, Y.: A simpler linear-time recognition of circular-arc graphs. In: 10th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol.\u00a04059, pp.\u00a041\u201352. Springer, Berlin (2006)"},{"issue":"7","key":"9432_CR11","doi-asserted-by":"crossref","first-page":"810","DOI":"10.2307\/2317880","volume":"76","author":"V. Klee","year":"1969","unstructured":"Klee, V.: What are the intersections graphs of arcs in a circle? Am. Math. Mon. 76(7), 810\u2013813 (1969)","journal-title":"Am. Math. Mon."},{"key":"9432_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/11809678_10","volume-title":"12th Annual International Computing and Combinatorics Conference (COCOON)","author":"M.C. Lin","year":"2006","unstructured":"Lin, M.C., Szwarcfiter, J.L.: Characterizations and linear time recognition of helly circular-arc graphs. In: 12th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol.\u00a04112, pp.\u00a073\u201382. Springer, Berlin (2006)"},{"key":"9432_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/3-540-53832-1_31","volume-title":"16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"T.-H. Ma","year":"1991","unstructured":"Ma, T.-H., Spinrad, J.P.: Avoiding matrix multiplication. In: 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol.\u00a0484, pp.\u00a061\u201371. Springer, Berlin (1991)"},{"issue":"2","key":"9432_CR14","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"9432_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"9432_CR16","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of probe interval models. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0866\u2013875 (2002)"},{"issue":"3","key":"9432_CR17","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0095-8956(88)90038-X","volume":"44","author":"J.P. Spinrad","year":"1988","unstructured":"Spinrad, J.P.: Circular-arc graphs with clique cover number two. J. Comb. Theory, Ser. B 44(3), 300\u2013306 (1988)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9432_CR18","series-title":"Fields Institute Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, vol.\u00a019. American Mathematical Society, Providence (2003)"},{"key":"9432_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1007\/BFb0036947","volume-title":"10th International Colloquium on Automata, Languages and Programming (ICALP)","author":"J.P. Spinrad","year":"1983","unstructured":"Spinrad, J.P., Valdes, J.: Recognition and isomorphism of two dimensional partial orders. In: 10th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol.\u00a0154, pp.\u00a0676\u2013686. Springer, Berlin (1983)"},{"key":"9432_CR20","doi-asserted-by":"crossref","unstructured":"Stefanakos, S., Erlebach, T.: Routing in all-optical ring networks revisited. In: Proceedings of the 9th IEEE Symposium on Computers and Communication, pp. 288\u2013293 (2004)","DOI":"10.1109\/ISCC.2004.1358419"},{"issue":"2","key":"9432_CR21","doi-asserted-by":"crossref","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"A.C. Tucker","year":"1971","unstructured":"Tucker, A.C.: Matrix characterizations of circular-arc graphs. Pac. J. Math. 39(2), 535\u2013545 (1971)","journal-title":"Pac. J. Math."},{"issue":"1","key":"9432_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A.C. Tucker","year":"1980","unstructured":"Tucker, A.C.: An efficient test for circular-arc graphs. SIAM J. Comput. 9(1), 1\u201324 (1980)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9432-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9432-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T23:29:29Z","timestamp":1711668569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9432-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,3]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9432"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9432-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,3]]}}}