{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:53Z","timestamp":1759637753063},"reference-count":33,"publisher":"Elsevier BV","issue":"50","license":[{"start":{"date-parts":[[2011,11,1]],"date-time":"2011-11-01T00:00:00Z","timestamp":1320105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2015,11,25]],"date-time":"2015-11-25T00:00:00Z","timestamp":1448409600000},"content-version":"vor","delay-in-days":1485,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2011,11]]},"DOI":"10.1016\/j.tcs.2011.09.010","type":"journal-article","created":{"date-parts":[[2011,9,16]],"date-time":"2011-09-16T19:20:35Z","timestamp":1316200835000},"page":"6982-7000","source":"Crossref","is-referenced-by-count":20,"title":["Dominating set is fixed parameter tractable in claw-free graphs"],"prefix":"10.1016","volume":"412","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.tcs.2011.09.010_br000005","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","article-title":"Linear time algorithms for finding a dominating set of fixed size in degenerated graphs","volume":"54","author":"Alon","year":"2009","journal-title":"Algorithmica"},{"issue":"2","key":"10.1016\/j.tcs.2011.09.010_br000010","doi-asserted-by":"crossref","DOI":"10.1145\/1721837.1721856","article-title":"Optimization problems in multiple-interval graphs","volume":"6","author":"Butman","year":"2010","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"10.1016\/j.tcs.2011.09.010_br000015","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1016\/j.jctb.2007.02.002","article-title":"Claw-free graphs. I. Orientable prismatic graphs","volume":"97","author":"Chudnovsky","year":"2007","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.tcs.2011.09.010_br000020","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.jctb.2007.06.006","article-title":"Claw-free graphs. II. Non-orientable prismatic graphs","volume":"98","author":"Chudnovsky","year":"2008","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"10.1016\/j.tcs.2011.09.010_br000025","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.jctb.2008.03.001","article-title":"Claw-free graphs. III. Circular interval graphs","volume":"98","author":"Chudnovsky","year":"2008","journal-title":"J. Combin. Theory Ser. B"},{"issue":"5","key":"10.1016\/j.tcs.2011.09.010_br000030","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1016\/j.jctb.2007.06.007","article-title":"Claw-free graphs. IV. Decomposition theorem","volume":"98","author":"Chudnovsky","year":"2008","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"10.1016\/j.tcs.2011.09.010_br000035","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.jctb.2008.03.002","article-title":"Claw-free graphs. V. Global structure","volume":"98","author":"Chudnovsky","year":"2008","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"10.1016\/j.tcs.2011.09.010_br000040","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1016\/j.jctb.2010.04.005","article-title":"Claw-free graphs VI. Colouring","volume":"100","author":"Chudnovsky","year":"2010","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.tcs.2011.09.010_br000045","series-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B)","first-page":"193","article-title":"Graph rewriting: an algebraic and logic approach","author":"Courcelle","year":"1990"},{"key":"10.1016\/j.tcs.2011.09.010_br000050","doi-asserted-by":"crossref","unstructured":"Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub\u00a0Onufry Wojtaszczyk, Dominating set is fixed parameter tractable in claw-free graphs. CoRR, abs\/1011.6239, 2010.","DOI":"10.1016\/j.tcs.2011.09.010"},{"key":"10.1016\/j.tcs.2011.09.010_br000055","series-title":"LICS","first-page":"270","article-title":"Locally excluding a minor","author":"Dawar","year":"2007"},{"key":"10.1016\/j.tcs.2011.09.010_br000060","unstructured":"Anuj Dawar, Stephan Kreutzer, Domination problems in nowhere-dense classes, in: Ravi Kannan, K.\u00a0Narayan Kumar (Eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 4, Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2009, pp. 157\u2013168."},{"key":"10.1016\/j.tcs.2011.09.010_br000065","series-title":"Complexity Theory: Current Research","first-page":"191","article-title":"Fixed parameter tractability and completeness","author":"Downey","year":"1992"},{"key":"10.1016\/j.tcs.2011.09.010_br000070","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/j.tcs.2011.09.010_br000075","series-title":"FOCS","first-page":"133","article-title":"Deciding first-order properties for sparse graphs","author":"Dvorak","year":"2010"},{"issue":"3","key":"10.1016\/j.tcs.2011.09.010_br000080","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321765.321781","article-title":"Loopless algorithms for generating permutations, combinations, and other combinatorial configurations","volume":"20","author":"Ehrlich","year":"1973","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2011.09.010_br000085","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.jalgor.2004.02.001","article-title":"The dominating set problem is fixed parameter tractable for graphs of bounded genus","volume":"52","author":"Ellis","year":"2004","journal-title":"J. Algorithms"},{"key":"10.1016\/j.tcs.2011.09.010_br000090","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","article-title":"Claw-free graphs \u2014 a survey","volume":"164","author":"Faudree","year":"1997","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/j.tcs.2011.09.010_br000095","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/S0097539799360768","article-title":"Fixed-parameter tractability, definability, and model-checking","volume":"31","author":"Flum","year":"2001","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2011.09.010_br000100","series-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"issue":"2","key":"10.1016\/j.tcs.2011.09.010_br000105","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/S0097539702419649","article-title":"Dominating sets in planar graphs: Branch-width and exponential speed-up","volume":"36","author":"Fomin","year":"2006","journal-title":"SIAM J. Comput."},{"issue":"6","key":"10.1016\/j.tcs.2011.09.010_br000110","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","article-title":"Deciding first-order properties of locally tree-decomposable structures","volume":"48","author":"Frick","year":"2001","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2011.09.010_br000115","series-title":"Computers and Intractability: A Guide to the Theory of NP\u2013Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/j.tcs.2011.09.010_br000120","series-title":"Proceedings of the 3rd Conference on Discrete Mathematics (1986)","first-page":"205","article-title":"Recent results and open problems in domination theory","author":"Hedetniemi","year":"1988"},{"key":"10.1016\/j.tcs.2011.09.010_br000125","series-title":"ICALP (1)","first-page":"462","article-title":"Domination when the stars are out","volume":"vol. 6755","author":"Hermelin","year":"2011"},{"key":"10.1016\/j.tcs.2011.09.010_br000130","series-title":"Extremal Combinatorics \u2014 With Applications in Computer Science","author":"Jukna","year":"2001"},{"key":"10.1016\/j.tcs.2011.09.010_br000135","series-title":"Complexity of Computer Communications","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"issue":"3","key":"10.1016\/j.tcs.2011.09.010_br000140","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","article-title":"On maximal independent sets of vertices in claw-free graphs","volume":"28","author":"Minty","year":"1980","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.tcs.2011.09.010_br000145","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","article-title":"Graph minors. XVI. Excluding a non-planar graph","volume":"89","author":"Robertson","year":"2003","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.tcs.2011.09.010_br000150","series-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier","year":"2006"},{"key":"10.1016\/j.tcs.2011.09.010_br000155","series-title":"Algorithms \u2014 ESA 2009","first-page":"694","article-title":"Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels","volume":"vol. 5757","author":"Philip","year":"2009"},{"issue":"1","key":"10.1016\/j.tcs.2011.09.010_br000160","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","article-title":"Algorithme de recherche d\u2019un stable de cardinalite maximum dans un graphe sans etoile","volume":"29","author":"Sbihi","year":"1980","journal-title":"Discrete Math."},{"issue":"6","key":"10.1016\/j.tcs.2011.09.010_br000165","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","article-title":"Linear time computable problems and first-order descriptions","volume":"6","author":"Seese","year":"1996","journal-title":"Math. Struct. Comput. Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397511007766?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397511007766?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,12,5]],"date-time":"2021-12-05T06:20:44Z","timestamp":1638685244000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397511007766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":33,"journal-issue":{"issue":"50","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["S0304397511007766"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2011.09.010","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}