{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:57Z","timestamp":1760441097496},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_31","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"308-319","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Domination in Circle Graphs"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Gon\u00e7alves","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"issue":"4","key":"31_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed Parameter Algorithms for Dominated Set and Related Problems on Planar Graphs. Algorithmica\u00a033(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"31_CR3","unstructured":"Alon, N., Gutner, S.: Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. Electronic Colloquium on Computational Complexity (ECCC)\u00a015(066) (2008)"},{"issue":"8","key":"31_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Gon\u00e7alves, D., Mertzios, G.B., Paul, C., Sau, I., Thomass\u00e9, S.: Parameterized Domination in Circle Graphs. Manuscript available at \n                    \n                      http:\/\/arxiv.org\/abs\/1205.3728\n                    \n                    \n                   (2012)","DOI":"10.1007\/978-3-642-34611-8_31"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-50728-0_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"1989","unstructured":"Courcelle, B.: The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs. In: van Leeuwen, J. (ed.) WG 1988. LNCS, vol.\u00a0344, pp. 30\u201353. Springer, Heidelberg (1989)"},{"issue":"50","key":"31_CR7","doi-asserted-by":"publisher","first-page":"6982","DOI":"10.1016\/j.tcs.2011.09.010","volume":"412","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theoretical Computer Science\u00a0412(50), 6982\u20137000 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"31_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(89)90059-8","volume":"32","author":"P. Damaschke","year":"1989","unstructured":"Damaschke, P.: The Hamiltonian Circuit Problem for Circle Graphs is NP-Complete. Information Processing Letters\u00a032(1), 1\u20132 (1989)","journal-title":"Information Processing Letters"},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/3-540-46632-0_7","volume-title":"Algorithms and Computations","author":"M. Damian-Iordache","year":"1999","unstructured":"Damian-Iordache, M., Pemmaraju, S.V.: Hardness of Approximating Independent Domination in Circle Graphs. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 56\u201369. Springer, Heidelberg (1999)"},{"key":"31_CR10","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)"},{"issue":"1-3","key":"31_CR11","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0166-218X(93)90222-A","volume":"44","author":"E.S. Elmallah","year":"1993","unstructured":"Elmallah, E.S., Stewart, L.K.: Independence and domination in polygon graphs. Discrete Applied Mathematics\u00a044(1-3), 65\u201377 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A.: Queues, stacks and graphs. In: Press, A. (ed.) Theory of Machines and Computations, pp. 71\u201386 (1971)","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"issue":"1","key":"31_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science\u00a0410(1), 53\u201361 (2009)","journal-title":"Theoretical Computer Science"},{"key":"31_CR14","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-642-29344-3_30","volume-title":"LATIN 2012: Theoretical Informatics","author":"F. Fomin","year":"2012","unstructured":"Fomin, F., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., Jan Van Leeuwen, E., Vatshelle, M., Villanger, Y.: k-Gap Interval Graphs. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 350\u2013361. Springer, Heidelberg (2012), \n                    \n                      http:\/\/arxiv.org\/abs\/1112.3244"},{"key":"31_CR16","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. W.H. Freeman, San Francisco (1979)"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks\u00a03, 261\u2013273 (1973)","journal-title":"Networks"},{"issue":"1","key":"31_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2007.12.003","volume":"107","author":"F. Gavril","year":"2008","unstructured":"Gavril, F.: Minimum weight feedback vertex sets in circle graphs. Information Processing Letters\u00a0107(1), 1\u20136 (2008)","journal-title":"Information Processing Letters"},{"key":"31_CR19","unstructured":"Gioan, E., Paul, C., Tedder, M., Corneil, D.: Circle Graph Recognition in Time O(n\u2009+\u2009m)\u00b7\u03b1(n\u2009+\u2009m). Manuscript available at \n                    \n                      http:\/\/arxiv.org\/abs\/1104.3284\n                    \n                    \n                   (2011)"},{"issue":"1-3","key":"31_CR20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0012-365X(00)00012-1","volume":"222","author":"S.M. Hedetniemi","year":"2000","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Rall, D.F.: Acyclic domination. Discrete Mathematics\u00a0222(1-3), 151\u2013165 (2000)","journal-title":"Discrete Mathematics"},{"key":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-28050-4_3","volume-title":"Parameterized and Exact Computation","author":"M. Jiang","year":"2012","unstructured":"Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-Interval Graphs: Domination. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 27\u201340. Springer, Heidelberg (2012)"},{"issue":"1","key":"31_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"J.M. Keil","year":"1993","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Applied Mathematics\u00a042(1), 51\u201363 (1993)","journal-title":"Discrete Applied Mathematics"},{"issue":"14","key":"31_CR23","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1016\/j.dam.2006.03.003","volume":"154","author":"J.M. Keil","year":"2006","unstructured":"Keil, J.M., Stewart, L.: Approximating the minimum clique cover and other hard problems in subtree filament graphs. Discrete Applied Mathematics\u00a0154(14), 1983\u20131995 (2006)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"31_CR24","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1142\/S0129054196000099","volume":"7","author":"T. Kloks","year":"1996","unstructured":"Kloks, T.: Treewidth of circle graphs. International Journal of Foundations of Computer Science\u00a07(2), 111\u2013120 (1996)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"31_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Parameterized and Exact Computation","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized Complexity of Independence and Domination on Geometric Graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 154\u2013165. Springer, Heidelberg (2006)"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Sherwani, N.A.: Algorithms for VLSI Physical Design Automation. Kluwer Academic Press (1992)","DOI":"10.1007\/978-1-4757-2219-2"},{"issue":"2","key":"31_CR28","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J. Spinrad","year":"1994","unstructured":"Spinrad, J.: Recognition of circle graphs. Journal of Algorithms\u00a016(2), 264\u2013282 (1994)","journal-title":"Journal of Algorithms"},{"key":"31_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0035832","volume-title":"STACS 88","author":"W. Unger","year":"1988","unstructured":"Unger, W.: On the k-Colouring of Circle-Graphs. In: Cori, R., Wirsing, M. (eds.) STACS 1988. LNCS, vol.\u00a0294, pp. 61\u201372. Springer, Heidelberg (1988)"},{"key":"31_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/3-540-55210-3_199","volume-title":"STACS 92","author":"W. Unger","year":"1992","unstructured":"Unger, W.: The Complexity of Colouring Circle Graphs (Extended Abstract). In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol.\u00a0577, pp. 389\u2013400. Springer, Heidelberg (1992)"},{"issue":"4","key":"31_CR31","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.ipl.2006.04.002","volume":"99","author":"G. Xu","year":"2006","unstructured":"Xu, G., Kang, L., Shan, E.: Acyclic domination on bipartite permutation graphs. Information Processing Letters\u00a099(4), 139\u2013144 (2006)","journal-title":"Information Processing Letters"}],"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-642-34611-8_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:00:49Z","timestamp":1620133249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}