{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:41:45Z","timestamp":1725522105915},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922476"},{"type":"electronic","value":"9783540922483"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92248-3_29","type":"book-chapter","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T08:36:17Z","timestamp":1228379777000},"page":"324-335","source":"Crossref","is-referenced-by-count":0,"title":["From a Circular-Arc Model to a Proper Circular-Arc Model"],"prefix":"10.1007","author":[{"given":"Yahav","family":"Nussbaum","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X. Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs. SIAM J. Comput.\u00a025, 390\u2013403 (1996)","journal-title":"SIAM J. Comput."},{"key":"29_CR2","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"M.C. Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in Circular Arc Graphs. J. Algorithms\u00a09, 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"key":"29_CR4","doi-asserted-by":"publisher","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.\u00a024, 411\u2013439 (1995)","journal-title":"SIAM J. Comput."},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W.L. Hsu","year":"1991","unstructured":"Hsu, W.L., Tsai, K.H.: Linear Time Algorithms on Circular-Arc Graphs. Info. Proc. Lett.\u00a040, 123\u2013129 (1991)","journal-title":"Info. Proc. Lett."},{"key":"29_CR6","unstructured":"Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L.: Linear Time Recognition of Helly Circular-Arc Models and Graphs (submitted)"},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/11917496_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Kaplan","year":"2006","unstructured":"Kaplan, H., Nussbaum, Y.: Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 289\u2013300. Springer, Heidelberg (2006)"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11785293_7","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"H. Kaplan","year":"2006","unstructured":"Kaplan, H., Nussbaum, Y.: A Simpler Linear-Time Recognition of Circular-Arc Graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 41\u201352. Springer, Heidelberg (2006)"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/1109557.1109592","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006","author":"M.C. Lin","year":"2006","unstructured":"Lin, M.C., Szwarcfiter, J.L.: Efficient Construction of Unit Circular-Arc Models. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 309\u2013315. ACM Press, New York (2006)"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-540-74839-7_24","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.C. Lin","year":"2007","unstructured":"Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Proper Helly Circular-Arc Graphs. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 248\u2013257. Springer, Heidelberg (2007)"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1002\/net.10014","volume":"39","author":"G.K. Manacher","year":"2002","unstructured":"Manacher, G.K., Mankus, T.A.: A Simple Linear Time Algorithm for Finding a Maximum Independent Set of Circular Arcs Using Intervals Alone. Networks\u00a039, 68\u201372 (2002)","journal-title":"Networks"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0217003","volume":"17","author":"S. Masuda","year":"1988","unstructured":"Masuda, S., Nakajima, K.: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph. SIAM J. Comput.\u00a017, 41\u201352 (1988)","journal-title":"SIAM J. Comput."},{"key":"29_CR13","doi-asserted-by":"publisher","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\u00a037, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"29_CR14","first-page":"139","volume-title":"Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Conference","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference Graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Conference, pp. 139\u2013146. Academic Press, London (1969)"},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0166-218X(89)90011-5","volume":"25","author":"W.K. Shih","year":"1989","unstructured":"Shih, W.K., Hsu, W.L.: An O(n\n                  1.5) Algorithm to Color Proper Circular Arcs. Discrete Applied Mathematics\u00a025, 321\u2013323 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR16","volume-title":"Fields Institute Monographs","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. In: Fields Institute Monographs, vol.\u00a019. American Mathematical Society, Providence (2003)"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(74)80027-0","volume":"7","author":"A. Tucker","year":"1974","unstructured":"Tucker, A.: Structure Theorems for Some Classes of Circular-Arc Graphs. Discrete Mathematics\u00a07, 167\u2013195 (1974)","journal-title":"Discrete Mathematics"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"Tucker, A.: An Efficient Test for Circular-Arc Graphs. SIAM J. Comput.\u00a09, 1\u201324 (1980)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92248-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T03:05:28Z","timestamp":1551668728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92248-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922476","9783540922483"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92248-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}