{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:23:42Z","timestamp":1725600222186},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642222993"},{"type":"electronic","value":"9783642223006"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_2","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T08:41:31Z","timestamp":1312879291000},"page":"13-24","source":"Crossref","is-referenced-by-count":1,"title":["A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs"],"prefix":"10.1007","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasine","family":"Babu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00373-010-0922-0","volume":"26","author":"A.A. Abueida","year":"2010","unstructured":"Abueida, A.A., Busch, A.H., Sritharan, R.: A min-max property of chordal bipartite graphs with applications. Graphs and Combinatorics\u00a026(3), 301\u2013313 (2010)","journal-title":"Graphs and Combinatorics"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Adiga, A., Babu, J., Chandran, L.S.: A constant factor approximation algorithm for boxicity of circular arc graphs. In: CoRR, abs\/1102.1544 (February 2011), http:\/\/arxiv.org\/abs\/1102.1544","DOI":"10.1007\/978-3-642-22300-6_2"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1016\/j.dam.2010.06.017","volume":"158","author":"A. Adiga","year":"2010","unstructured":"Adiga, A., Bhowmick, D., Sunil Chandran, L.: The hardness of approximating the boxicity, cubicity and threshold dimension of a graph. Discrete Appl. Math.\u00a0158, 1719\u20131726 (2010)","journal-title":"Discrete Appl. Math."},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K. Cameron","year":"2003","unstructured":"Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math.\u00a0266, 133\u2013142 (2003)","journal-title":"Discrete Math."},{"issue":"8","key":"2_CR5","doi-asserted-by":"publisher","first-page":"2488","DOI":"10.1016\/j.disc.2008.06.003","volume":"309","author":"L.S. Chandran","year":"2009","unstructured":"Chandran, L.S., Das, A., Shah, C.D.: Cubicity, boxicity, and vertex cover. Discrete Mathematics\u00a0309(8), 2488\u20132496 (2009)","journal-title":"Discrete Mathematics"},{"key":"2_CR6","unstructured":"Cozzens, M.B.: Higher and multi-dimensional analogues of interval graphs. Ph.D. thesis, Department of Mathematics. Rutgers University, New Brunswick, NJ (1981)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica\u00a019, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"key":"2_CR8","first-page":"115","volume-title":"Theory of Graphs","author":"T. Gallai","year":"1968","unstructured":"Gallai, T.: On directed paths and circuits. In: Erd\u00f6s, P., Katona, G. (eds.) Theory of Graphs, pp. 115\u2013118. Academic Press, New York (1968)"},{"issue":"2","key":"2_CR9","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Alg. Disc. Meth.\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Appl. Math.\u00a0101, 157\u2013165 (2000)","journal-title":"Discrete Appl. Math."},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20006","volume":"46","author":"P. Hell","year":"2004","unstructured":"Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. J. Graph Theory\u00a046, 313\u2013327 (2004)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math.\u00a052(3), 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"18","key":"2_CR13","doi-asserted-by":"publisher","first-page":"5618","DOI":"10.1016\/j.disc.2008.04.003","volume":"309","author":"M.C. Lin","year":"2009","unstructured":"Lin, M.C., Szwarcfiter, J.L.: Characterizations and recognition of circular-arc graphs and subclasses: A survey. Discrete Mathematics\u00a0309(18), 5618\u20135635 (2009)","journal-title":"Discrete Mathematics"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/11682462_66","volume-title":"LATIN 2006: Theoretical Informatics","author":"F. Mazoit","year":"2006","unstructured":"Mazoit, F.: The branch-width of circular-arc graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 727\u2013736. Springer, Heidelberg (2006)"},{"issue":"2","key":"2_CR15","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(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"2_CR16","first-page":"301","volume-title":"Recent Progresses in Combinatorics","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301\u2013310. Academic Press, New York (1969)"},{"key":"2_CR17","first-page":"127","volume":"9","author":"B. Rosgen","year":"2007","unstructured":"Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discrete Mathematics and Theoretical Computer Science\u00a09, 127\u2013136 (2007)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"2_CR18","unstructured":"Scheinerman, E.R.: Intersection classes and multiple intersection parameters of graphs. Ph.D. thesis. Princeton University (1984)"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-74839-7_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K. Suchan","year":"2007","unstructured":"Suchan, K., Todinca, I.: Pathwidth of circular-arc graphs. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 258\u2013269. Springer, Heidelberg (2007)"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0895480191193789","volume":"7","author":"R. Sundaram","year":"1994","unstructured":"Sundaram, R., Singh, K.S., Rangan, C.P.: Treewidth of circular-arc graphs. SIAM J. Discret. Math.\u00a07, 647\u2013655 (1994)","journal-title":"SIAM J. Discret. Math."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0095-8956(86)90061-4","volume":"40","author":"C. Thomassen","year":"1986","unstructured":"Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B\u00a040, 9\u201320 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"19","author":"A.C. Tucker","year":"1971","unstructured":"Tucker, A.C.: Matrix characterizations of circular-arc graphs. Pacific J. of Mathematics\u00a019, 535\u2013545 (1971)","journal-title":"Pacific J. of Mathematics"},{"issue":"1,2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(74)80027-0","volume":"7","author":"A.C. Tucker","year":"1974","unstructured":"Tucker, A.C.: Structure theorems for some circular-arc graphs. Discrete Mathematics\u00a07(1,2), 167\u2013195 (1974)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"2_CR24","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Alg. Disc. Meth.\u00a03(3), 351\u2013358 (1982)","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"1-2","key":"2_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(97)00036-4","volume":"205","author":"C.W. Yu","year":"1998","unstructured":"Yu, C.W., Chen, G.H., Ma, T.H.: On the complexity of the -chain subgraph cover problem. Theor. Comput. Sci.\u00a0205(1-2), 85\u201398 (1998)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T20:38:01Z","timestamp":1638218281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}