{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:03Z","timestamp":1759063743673},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,5,11]],"date-time":"2013-05-11T00:00:00Z","timestamp":1368230400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00224-013-9478-8","type":"journal-article","created":{"date-parts":[[2013,5,10]],"date-time":"2013-05-10T07:04:11Z","timestamp":1368169451000},"page":"45-72","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Domination in Circle Graphs"],"prefix":"10.1007","volume":"54","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","published-online":{"date-parts":[[2013,5,11]]},"reference":[{"key":"9478_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"issue":"4","key":"9478_CR2","doi-asserted-by":"crossref","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 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"9478_CR3","unstructured":"Alon, N., Gutner, S.: Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. Electronic Colloquium on Computational Complexity (ECCC) 15(066) (2008)"},{"key":"9478_CR4","series-title":"LNCS","first-page":"29","volume-title":"Proc. of the 6th Workshop on Approximation and On-Line Algorithms (ALGO\/WAOA)","author":"O. Amini","year":"2008","unstructured":"Amini, O., Peleg, D., P\u00e9rennes, S., Sau, I., Saurabh, S.: Degree-constrained subgraph problems: hardness and approximation. In: Proc. of the 6th Workshop on Approximation and On-Line Algorithms (ALGO\/WAOA). LNCS, vol.\u00a05426, pp.\u00a029\u201342 (2008)"},{"issue":"8","key":"9478_CR5","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9478_CR6","series-title":"LNCS","first-page":"30","volume-title":"Proc. of the 14th International Workshop on Graph-theoretic Concepts in Computer Science (WG)","author":"B. Courcelle","year":"1988","unstructured":"Courcelle, B.: The monadic second-order logic of graphs: definable sets of finite graphs. In: Proc. of the 14th International Workshop on Graph-theoretic Concepts in Computer Science (WG). LNCS, vol.\u00a0344, pp.\u00a030\u201353 (1988)"},{"issue":"50","key":"9478_CR7","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 412(50), 6982\u20137000 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9478_CR8","doi-asserted-by":"crossref","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. Inf. Process. Lett. 32(1), 1\u20132 (1989)","journal-title":"Inf. Process. Lett."},{"key":"9478_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/3-540-46632-0_7","volume-title":"10th International Symposium on Algorithms and Computation (ISAAC)","author":"M. Damian-Iordache","year":"1999","unstructured":"Damian-Iordache, M., Pemmaraju, S.V.: Hardness of approximating independent domination in circle graphs. In: 10th International Symposium on Algorithms and Computation (ISAAC). LNCS, vol.\u00a01741, pp.\u00a056\u201369 (1999)"},{"key":"9478_CR10","doi-asserted-by":"crossref","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\u20133","key":"9478_CR11","doi-asserted-by":"crossref","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 Appl. Math. 44(1\u20133), 65\u201377 (1993)","journal-title":"Discrete Appl. Math."},{"key":"9478_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/B978-0-12-417750-5.50011-7","volume-title":"Theory of Machines and Computations","author":"S. Even","year":"1971","unstructured":"Even, S., Itai, A.: Queues, stacks and graphs. In: Press, A. (ed.) Theory of Machines and Computations, pp.\u00a071\u201386 (1971)"},{"issue":"1","key":"9478_CR13","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9478_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P. Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"key":"9478_CR15","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9478_CR16","volume-title":"Proc. of the 10th Latin American Theoretical INformatics Symposium (LATIN)","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: Proc. of the 10th Latin American Theoretical INformatics Symposium (LATIN) (2012). Available at: arXiv:1112.3244"},{"key":"9478_CR17","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":"9478_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1644015.1644024","volume":"6","author":"S. Gaspers","year":"2009","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M., Todinca, I.: Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans. Algorithms 6, 1 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"9478_CR19","doi-asserted-by":"crossref","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 3, 261\u2013273 (1973)","journal-title":"Networks"},{"issue":"1","key":"9478_CR20","doi-asserted-by":"crossref","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. Inf. Process. Lett. 107(1), 1\u20136 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9478_CR21","unstructured":"Gioan, E., Paul, C., Tedder, M., Corneil, D.: Circle Graph Recognition in Time O(n+m)\u22c5\u03b1(n+m) (2011). Manuscript available at: arXiv:1104.3284"},{"issue":"1\u20133","key":"9478_CR22","doi-asserted-by":"crossref","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 Math. 222(1\u20133), 151\u2013165 (2000)","journal-title":"Discrete Math."},{"key":"9478_CR23","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/978-3-642-22006-7_39","volume-title":"Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP)","author":"D. Hermelin","year":"2011","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. In: Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a06755, pp.\u00a0462\u2013473 (2011)"},{"key":"9478_CR24","series-title":"LNCS","first-page":"27","volume-title":"Proc. of the 6th International Symposium on Parameterized and Exact Computation (IPEC)","author":"M. Jiang","year":"2011","unstructured":"Jiang, M., Zhang, Y.: Parameterized complexity in multiple-interval graphs: domination. In: Proc. of the 6th International Symposium on Parameterized and Exact Computation (IPEC). LNCS, vol.\u00a07112, pp.\u00a027\u201340 (2011)"},{"issue":"1","key":"9478_CR25","doi-asserted-by":"crossref","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 Appl. Math. 42(1), 51\u201363 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"14","key":"9478_CR26","doi-asserted-by":"crossref","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 Appl. Math. 154(14), 1983\u20131995 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9478_CR27","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1142\/S0129054196000099","volume":"7","author":"T. Kloks","year":"1996","unstructured":"Kloks, T.: Treewidth of circle graphs. Int. J. Found. Comput. Sci. 7(2), 111\u2013120 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9478_CR28","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Proc. of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC)","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Proc. of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC). LNCS, vol.\u00a04169, pp.\u00a0154\u2013165 (2006)"},{"key":"9478_CR29","doi-asserted-by":"crossref","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 University Press, Oxford (2006)"},{"key":"9478_CR30","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Nondeterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15, 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9478_CR31","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9478_CR32","series-title":"LNCS","first-page":"566","volume-title":"Proc. of the 17th Annual European Symposium on Algorithms (ESA)","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Proc. of the 17th Annual European Symposium on Algorithms (ESA). LNCS, vol.\u00a05757, pp.\u00a0566\u2013577 (2009)"},{"key":"9478_CR33","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/978-3-642-14165-2_32","volume-title":"Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP)","author":"J. Ru\u00e9","year":"2010","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. In: Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a06198, pp.\u00a0372\u2013383 (2010)"},{"key":"9478_CR34","volume-title":"Algorithms for VLSI Physical Design Automation","author":"N.A. Sherwani","year":"1992","unstructured":"Sherwani, N.A.: Algorithms for VLSI Physical Design Automation. Kluwer Academic, Norwell (1992)"},{"issue":"2","key":"9478_CR35","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J. Spinrad","year":"1994","unstructured":"Spinrad, J.: Recognition of circle graphs. J. Algorithms 16(2), 264\u2013282 (1994)","journal-title":"J. Algorithms"},{"key":"9478_CR36","series-title":"LNCS","first-page":"61","volume-title":"Proc. of the 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"W. Unger","year":"1988","unstructured":"Unger, W.: On the k-colouring of circle-graphs. In: Proc. of the 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS). LNCS, vol.\u00a0294, pp.\u00a061\u201372 (1988)"},{"key":"9478_CR37","series-title":"LNCS","first-page":"389","volume-title":"Proc. of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"W. Unger","year":"1992","unstructured":"Unger, W.: The complexity of colouring circle graphs (extended abstract). In: Proc. of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS). LNCS, vol.\u00a0577, pp.\u00a0389\u2013400 (1992)"},{"issue":"4","key":"9478_CR38","doi-asserted-by":"crossref","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. Inf. Process. Lett. 99(4), 139\u2013144 (2006)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9478-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9478-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9478-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:25Z","timestamp":1558698865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9478-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,11]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9478"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9478-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,11]]}}}