{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T14:46:44Z","timestamp":1766587604316},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175169"},{"type":"electronic","value":"9783642175176"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_33","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:13:41Z","timestamp":1291389221000},"page":"366-377","source":"Crossref","is-referenced-by-count":10,"title":["Parameterized Algorithms for Boxicity"],"prefix":"10.1007","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajesh","family":"Chitnis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-642-14031-0_3","volume-title":"COCOON 2010","author":"A. Adiga","year":"2010","unstructured":"Adiga, A., Bhowmick, D., Chandran, L.S.: Boxicity and poset dimension. In: Thai, T. (ed.) COCOON 2010. LNCS, vol.\u00a06196, pp. 3\u201312. Springer, Heidelberg (2010)"},{"issue":"16","key":"33_CR2","first-page":"1719","volume":"158","author":"A. Adiga","year":"2010","unstructured":"Adiga, A., Bhowmick, D., Chandran, L.S.: The hardness of approximating the threshold dimension, boxicity and cubicity of a graph. DAM\u00a0158(16), 1719\u20131726 (2010)","journal-title":"DAM"},{"key":"33_CR3","doi-asserted-by":"crossref","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)","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"33_CR4","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"33_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11847250_9","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: Conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 96\u2013108. Springer, Heidelberg (2006)"},{"key":"33_CR6","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. Disc. Math. 309, 2488\u20132496 (2009)","journal-title":"Disc. Math."},{"issue":"2","key":"33_CR7","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.jctb.2007.08.002","volume":"98","author":"L.S. Chandran","year":"2008","unstructured":"Chandran, L.S., Francis, M.C., Sivadasan, N.: Boxicity and maximum degree. J.\u00a0Comb. Theory Ser. B\u00a098(2), 443\u2013445 (2008)","journal-title":"J.\u00a0Comb. Theory Ser. B"},{"issue":"5","key":"33_CR8","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.jctb.2006.12.004","volume":"97","author":"L.S. Chandran","year":"2007","unstructured":"Chandran, L.S., Sivadasan, N.: Boxicity and treewidth. J.\u00a0Comb. Theory Ser. B\u00a097(5), 733\u2013744 (2007)","journal-title":"J.\u00a0Comb. Theory Ser. B"},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/11847250_16","volume-title":"Parameterized and Exact Computation","author":"Y. Chen","year":"2006","unstructured":"Chen, Y., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 175\u2013183. Springer, Heidelberg (2006)"},{"key":"33_CR10","volume-title":"Higher and multi-dimensional analogues of interval graphs, Ph.D. thesis","author":"M.B. Cozzens","year":"1981","unstructured":"Cozzens, M.B.: Higher and multi-dimensional analogues of interval graphs, Ph.D. thesis. Department of Mathematics, Rutgers University, New Brunswick (1981)"},{"key":"33_CR11","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0166-218X(83)90077-X","volume":"6","author":"M.B. Cozzens","year":"1983","unstructured":"Cozzens, M.B., Roberts, F.S.: Computing the boxicity of a graph by covering its complement by cointerval graphs. Disc. Appl. Math.\u00a06, 217\u2013228 (1983)","journal-title":"Disc. Appl. Math."},{"key":"33_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)"},{"key":"33_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R.G. Downey","year":"2006","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"issue":"5","key":"33_CR14","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1016\/j.ejc.2008.10.003","volume":"30","author":"L. Esperet","year":"2009","unstructured":"Esperet, L.: Boxicity of graphs with bounded degree. European J.\u00a0Combin.\u00a030(5), 1277\u20131280 (2009)","journal-title":"European J.\u00a0Combin."},{"issue":"4","key":"33_CR15","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst.\u00a045(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"key":"33_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"key":"33_CR17","series-title":"LNCS","volume-title":"TAMC 2009","author":"J. Fiala","year":"2009","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, Springer, Heidelberg (2009)"},{"key":"33_CR18","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"33_CR19","doi-asserted-by":"crossref","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SJDM\u00a04, 99\u2013106 (1991)","DOI":"10.1137\/0404010"},{"key":"33_CR20","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. Disc. Appl. Math.\u00a052, 233\u2013252 (1994)","journal-title":"Disc. Appl. Math."},{"key":"33_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/978-3-642-04128-0_58","volume-title":"Algorithms - ESA 2009","author":"D. Marx","year":"2009","unstructured":"Marx, D., Razgon, I.: Constant ratio fixed-parameter approximation of the edge multicut problem. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 647\u2013658. Springer, Heidelberg (2009)"},{"key":"33_CR22","series-title":"Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"33_CR23","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":"33_CR24","unstructured":"Scheinerman, E.R.: Intersection classes and multiple intersection parameters, Ph.D. thesis, Princeton University (1984)"},{"key":"33_CR25","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.\u00a0Comb. Theory Ser. B\u00a040, 9\u201320 (1986)","journal-title":"J.\u00a0Comb. Theory Ser. B"},{"issue":"3","key":"33_CR26","first-page":"351","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM\u00a0J.\u00a0Alg.\u00a0Disc.\u00a0Math.\u00a03(3), 351\u2013358 (1982)","journal-title":"SIAM\u00a0J.\u00a0Alg.\u00a0Disc.\u00a0Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T13:15:45Z","timestamp":1553260545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}