{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T08:46:22Z","timestamp":1746780382480},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2005,5]]},"DOI":"10.1007\/s10878-005-1411-x","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T20:57:18Z","timestamp":1119992238000},"page":"267-280","source":"Crossref","is-referenced-by-count":1,"title":["Perfect Circular Arc Coloring"],"prefix":"10.1007","volume":"9","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiquan","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenan","family":"Zang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1411_CR1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0196-6774(84)90028-2","volume":"5","author":"R.P. Anstee","year":"1984","unstructured":"R.P. Anstee and M. Farber, \u201cCharacterizations of totally balanced matrices,\u201d J. Algorithms, vol. 5, pp. 215\u2013230, 1984.","journal-title":"J. Algorithms"},{"key":"1411_CR2","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1006\/jagm.1997.0868","volume":"25","author":"B.K. Bhattacharya","year":"1997","unstructured":"B.K. Bhattacharya and D. Kaller, \u201cAn O(m + n log n) algorithm for the maximum-clique problem in circular-arc graphs,\u201d J. Algorithms, vol. 25, pp. 336\u2013358, 1997.","journal-title":"J. Algorithms"},{"key":"1411_CR3","unstructured":"M.-S. Chang, \u201cAlgorithms for maximum matching and minimum fill-in on chordal bipartite graphs,\u201d in Lecture Notes in Comput. Sci., vol. 1178, Springer, Berlin, 1996, pp. 146\u2013155."},{"key":"1411_CR4","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/S0895480101386723","volume":"17","author":"C.T. Cheng","year":"2004","unstructured":"C.T. Cheng, \u201cImproved approximation algorithms for the demand routing and slotting problem with unit demands on rings,\u201d SIAM J. Discrete Math., vol. 17, pp. 384\u2013402, 2004.","journal-title":"SIAM J. Discrete Math."},{"key":"1411_CR5","doi-asserted-by":"crossref","unstructured":"M. Chudnovsky, N. Robertson, P.D. Seymour, and R. Thomas, \u201cThe strong perfect graph theorem,\u201d Ann. of Math. (to appear).","DOI":"10.4007\/annals.2006.164.51"},{"key":"1411_CR6","doi-asserted-by":"crossref","unstructured":"F.F. Dragan, \u201cOn greedy matching ordering and greedy matchable graphs,\u201d in Lecture Notes in Comput. Sci., vol. 1335, Springer, Berlin, 1997, pp. 184\u2013198,","DOI":"10.1007\/BFb0024498"},{"key":"1411_CR7","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/S0166-218X(99)00149-3","volume":"99","author":"F.F. Dragan","year":"2000","unstructured":"F.F. Dragan, \u201cStrongly orderable graphs: A common generalization of strongly chordal and chordal bipartite graphs,\u201d Discrete Appl. Math., vol. 99, pp. 427\u2013442, 2000.","journal-title":"Discrete Appl. Math"},{"key":"1411_CR8","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"M. Farber, \u201cCharacterizations of strongly chordal graphs,\u201d Discrete Math., vol. 43, pp. 173\u2013189, 1983.","journal-title":"Discrete Math."},{"key":"1411_CR9","doi-asserted-by":"crossref","first-page":"217","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, \u201cThe complexity of coloring circular arcs and chords,\u201d SIAM J. Alg. Disc. Meth., vol. 1, pp. 217\u2013227, 1980.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"1411_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver, \u201cThe ellipsoid method and its consequences in combinatorial optimization,\u201d Combinatorica, vol. 1, pp. 169\u2013197, 1981.","journal-title":"Combinatorica"},{"key":"1411_CR11","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver, \u201cPolynomial algorithms for perfect graphs,\u201d Ann. Discrete Math., vol. 21, pp. 325\u2013356, 1984.","journal-title":"Ann. Discrete Math."},{"key":"1411_CR12","first-page":"189","volume":"11","author":"W.-L. Hsu","year":"1981","unstructured":"W.-L. Hsu, \u201cHow to color claw-free prefect graphs,\u201d Ann. Discrete Math., vol. 11, pp. 189\u2013197, 1981.","journal-title":"Ann. Discrete Math."},{"key":"1411_CR13","first-page":"306","volume":"70","author":"I.A. Karapetian","year":"1980","unstructured":"I.A. Karapetian, \u201cColoring of arc graphs,\u201d Akad. Nauk Armyan. SSR Dokl., vol. 70, pp. 306\u2013311, 1980.","journal-title":"Akad. Nauk Armyan. SSR Dokl."},{"key":"1411_CR14","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1007\/s00453-001-0023-9","volume":"30","author":"V. Kumar","year":"2001","unstructured":"V. Kumar, \u201cAn approximation algorithm for circular arc coloring,\u201d Algorithmica, vol. 30, pp. 406\u2013417, 2001.","journal-title":"Algorithmica"},{"key":"1411_CR15","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1137\/0216057","volume":"16","author":"A. Lubiw","year":"1987","unstructured":"A. Lubiw, \u201cDoubly lexical orderings of matrices,\u201d SIAM J. Comput., vol. 16, pp. 854\u2013879, 1987.","journal-title":"SIAM J. Comput."},{"key":"1411_CR16","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1002\/(SICI)1097-0118(200004)33:4<256::AID-JGT7>3.0.CO;2-2","volume":"33","author":"T. Niessen","year":"2000","unstructured":"T. Niessen and J. Kind, \u201cThe round-up property of the fractional chromatic number for proper circular arc graphs,\u201d J. Graph Theory, vol. 33, pp. 256\u2013267, 2000.","journal-title":"J. Graph Theory"},{"key":"1411_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, \u201cAn O(n2) algorithm for coloring proper circular arc graphs,\u201d SIAM J. Alg. Disc. Meth., vol. 2, pp. 88\u201393, 1981.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"1411_CR18","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0166-218X(89)90011-5","volume":"25","author":"W.-K. Shih","year":"1989","unstructured":"W.-K. Shih and W.-L. Hsu, \u201cAn O(n1.5) algorithm to color proper circular arcs,\u201d Discrete Appl. Math., vol. 25, pp. 321\u2013323, 1989.","journal-title":"Discrete Appl. Math."},{"key":"1411_CR19","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0020-0190(89)90220-2","volume":"31","author":"W.-K. Shih","year":"1989","unstructured":"W.-K. Shih and W.-L. Hsu, \u201cAn O(n log n+m log log n) maximum weight clique algorithm for circular-arc graphs,\u201d Inform. Process. Lett., vol. 31, pp. 129\u2013134, 1989.","journal-title":"Inform. Process. Lett."},{"key":"1411_CR20","unstructured":"W.-K. Shih and W.-L. Hsu, \u201cAn approximation algorithm for coloring circular-arc graphs,\u201d SIAM Conference on Discrete Mathematics, San Francisco, 1990."},{"key":"1411_CR21","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0012-365X(85)90052-4","volume":"25","author":"A. Teng","year":"1985","unstructured":"A. Teng and A. Tucker, \u201cAn O(qn) algorithm to q-Color a proper family of circular arcs,\u201d Discrete Math., vol. 25, pp. 233\u2013243, 1985.","journal-title":"Discrete Math."},{"key":"1411_CR22","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. Tucker","year":"1975","unstructured":"A. Tucker, \u201cColoring a family of circular arcs,\u201d SIAM J. Appl. Math., vol. 29, pp. 493\u2013502, 1975.","journal-title":"SIAM J. Appl. Math."},{"key":"1411_CR23","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1137\/S0097539700382157","volume":"32","author":"M. Valencia-Pabon","year":"2003","unstructured":"M. Valencia-Pabon, \u201cRevisiting Tucker\u2019s algorithm to color circular arc graphs,\u201d SIAM J. Comput., vol. 32, pp. 1067\u20131072, 2003.","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1411-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-005-1411-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1411-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T01:35:39Z","timestamp":1586309739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-005-1411-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["1411"],"URL":"https:\/\/doi.org\/10.1007\/s10878-005-1411-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]}}}