{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:16Z","timestamp":1759637956229},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,3,23]],"date-time":"2012-03-23T00:00:00Z","timestamp":1332460800000},"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":[[2013,6]]},"DOI":"10.1007\/s00453-012-9641-7","type":"journal-article","created":{"date-parts":[[2012,3,23]],"date-time":"2012-03-23T12:42:16Z","timestamp":1332506536000},"page":"369-396","source":"Crossref","is-referenced-by-count":1,"title":["A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs"],"prefix":"10.1007","volume":"66","author":[{"given":"Ching-Chi","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gen-Huey","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerard J.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,3,23]]},"reference":[{"issue":"3","key":"9641_CR1","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."},{"issue":"3","key":"9641_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0166-218X(96)00045-5","volume":"74","author":"L. Cai","year":"1997","unstructured":"Cai, L.: On spanning 2-trees in a graph. Discrete Appl. Math. 74(3), 203\u2013216 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9641_CR3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0166-218X(02)00417-1","volume":"131","author":"L. Cai","year":"2003","unstructured":"Cai, L.: The complexity of the locally connected spanning tree problem. Discrete Appl. Math. 131(1), 63\u201375 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9641_CR4","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/0605034","volume":"5","author":"G.J. Chang","year":"1984","unstructured":"Chang, G.J., Nemhauser, G.L.: The k-domination and k-stability problems on sun-free chordal graphs. SIAM J. Algebr. Discrete Methods 5, 332\u2013345 (1984)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"6","key":"9641_CR5","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M.-S. Chang","year":"1998","unstructured":"Chang, M.-S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"9641_CR6","unstructured":"Dietz, P.F.: Intersection graph algorithms. PhD thesis, Computer Science Department, Cornell University, Ithaca, NY (1984)"},{"issue":"2\u20133","key":"9641_CR7","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discrete Math. 43(2\u20133), 173\u2013189 (1983)","journal-title":"Discrete Math."},{"issue":"3","key":"9641_CR8","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1002\/net.3230110304","volume":"11","author":"A.M. Farley","year":"1981","unstructured":"Farley, A.M.: Networks immune to isolated failures. Networks 11(3), 255\u2013268 (1981)","journal-title":"Networks"},{"issue":"4","key":"9641_CR9","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230120404","volume":"12","author":"A.M. Farley","year":"1982","unstructured":"Farley, A.M., Proskurowski, A.: Networks immune to isolated line failures. Networks 12(4), 393\u2013403 (1982)","journal-title":"Networks"},{"key":"9641_CR10","series-title":"Annals of Discrete Mathematics","isbn-type":"print","first-page":"314","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. 57, p. 314. Elsevier, Amsterdam (2004). With a foreword by Claude Berge. ISBN\u00a00-444-51530-5","ISBN":"http:\/\/id.crossref.org\/isbn\/0444515305","edition":"2"},{"issue":"3","key":"9641_CR11","doi-asserted-by":"crossref","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 9(3), 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"issue":"4","key":"9641_CR12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459\u2013467 (1982)","journal-title":"Networks"},{"issue":"2","key":"9641_CR13","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jagm.1995.1031","volume":"19","author":"W.L. Hsu","year":"1995","unstructured":"Hsu, W.L., Spinrad, J.P.: Independent sets in circular-arc graphs. J. Algorithms 19(2), 145\u2013160 (1995)","journal-title":"J. Algorithms"},{"issue":"3","key":"9641_CR14","doi-asserted-by":"crossref","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. Inf. Process. Lett. 40(3), 123\u2013129 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9641_CR15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(92)90201-K","volume":"36","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M., Schaefer, D.: An optimal algorithm for finding dominating cycles in circular-arc graphs. Discrete Appl. Math. 36(1), 25\u201334 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"9641_CR16","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1137\/0219071","volume":"19","author":"D.T. Lee","year":"1990","unstructured":"Lee, D.T., Sarrafzadeh, M., Wu, Y.F.: Minimum cuts for circular-arc graphs. SIAM J. Comput. 19(6), 1041\u20131050 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9641_CR17","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.disc.2006.06.026","volume":"307","author":"C.-C. Lin","year":"2007","unstructured":"Lin, C.-C., Chang, G.J., Chen, G.-H.: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs. Discrete Math. 307(2), 208\u2013215 (2007)","journal-title":"Discrete Math."},{"issue":"1","key":"9641_CR18","doi-asserted-by":"crossref","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. 17(1), 41\u201352 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9641_CR19","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"},{"key":"9641_CR20","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Tree partition refinement algorithms. SIAM J. Comput. 16, 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9641_CR21","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BF02526033","volume":"18","author":"K.H. Tsai","year":"1997","unstructured":"Tsai, K.H., Lee, D.T.: k best cuts for circular-arc graphs. Algorithmica 18(2), 198\u2013216 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"9641_CR22","doi-asserted-by":"crossref","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. 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-012-9641-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9641-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9641-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:09Z","timestamp":1559137509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9641-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,23]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["9641"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9641-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,23]]}}}