{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:20:06Z","timestamp":1758273606360},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,2,13]],"date-time":"2008-02-13T00:00:00Z","timestamp":1202860800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,7]]},"DOI":"10.1007\/s10878-008-9141-5","type":"journal-article","created":{"date-parts":[[2008,2,12]],"date-time":"2008-02-12T12:56:00Z","timestamp":1202820960000},"page":"87-97","source":"Crossref","is-referenced-by-count":6,"title":["Parameterized dominating set problem in chordal graphs: complexity and lower bound"],"prefix":"10.1007","volume":"18","author":[{"given":"Chunmei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Yinglei","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,2,13]]},"reference":[{"issue":"2","key":"9141_CR1","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber J, Fiala J (2004) Geometric separation and exact solutions for the parameterized independent set problems on disks. J Algorithms 52(2):134\u2013151","journal-title":"J Algorithms"},{"issue":"3","key":"9141_CR2","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J Alber","year":"2004","unstructured":"Alber J, Fellows MR, Niedermeier R (2004) Polynomial time data reduction for dominating set. J ACM 51(3):363\u2013384","journal-title":"J ACM"},{"issue":"4","key":"9141_CR3","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 HL, Fernau H, Kloks T, Niedermeier R (2002) Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica 33(4):461\u2013493","journal-title":"Algorithmica"},{"key":"9141_CR4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg S, Proskurowski A (1989) Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl Math 23:11\u201324","journal-title":"Discrete Appl Math"},{"issue":"1","key":"9141_CR5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"KS Booth","year":"1980","unstructured":"Booth KS, Johnson JH (1980) Dominating set in chordal graphs. SIAM J Comput 11(1):191\u2013199","journal-title":"SIAM J Comput"},{"key":"9141_CR6","doi-asserted-by":"crossref","unstructured":"Chen J, Huang X, Kanj IA, Xia G (2004) Linear FPT reductions and computational lower bounds. In: Proceedings of the 36th annual ACM symposium on theory of computing, pp 212\u2013221","DOI":"10.1145\/1007352.1007391"},{"key":"9141_CR7","unstructured":"Chen J, Fernau H, Kanj IA, Xia G (2005) Parametric duality and kernalization: lower bounds and upper bounds on kernel size. In: Proceedings of the 22nd annual symposium on theoretical aspects of computer science, pp 269\u2013280"},{"issue":"6","key":"9141_CR8","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine ED, Fomin FV, Hajiaghayi MT, Thilikos DM (2005) Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J ACM 52(6):866\u2013893","journal-title":"J ACM"},{"key":"9141_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin"},{"key":"9141_CR10","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"G Fanica","year":"1965","unstructured":"Fanica G (1965) The intersection graph of subtrees in trees are exactly chordal graphs. Pac J Math 15:835\u2013855","journal-title":"Pac J Math"},{"key":"9141_CR11","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"issue":"99","key":"9141_CR12","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore PC, Hoffman AJ (1964) A characterization of comparability graphs and of interval graphs. Can J Math 16(99):539\u2013548","journal-title":"Can J Math"},{"key":"9141_CR13","doi-asserted-by":"crossref","unstructured":"Marx D (2005) The closest substring problem with small distances. In: Proceedings of the 46th annual symposium on foundations of computer science, pp 63\u201372","DOI":"10.1109\/SFCS.2005.70"},{"key":"9141_CR14","doi-asserted-by":"crossref","unstructured":"Marx D (2006) Parameterized complexity of independence and domination on geometric graphs. In: Proceedings of the 2nd workshop on parameterized and exact computation, pp 154\u2013165","DOI":"10.1007\/11847250_14"},{"key":"9141_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson N, Seymour PD (1986a) Graph minors II. Algorithmic aspects of tree-width. J Algorithms 7:309\u2013322","journal-title":"J Algorithms"},{"key":"9141_CR16","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson N, Seymour PD (1984) Graph minors III. Planar tree width. J Comb Theory Ser B 36:49\u201364","journal-title":"J Comb Theory Ser B"},{"key":"9141_CR17","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0095-8956(90)90120-O","volume":"48","author":"N Robertson","year":"1990","unstructured":"Robertson N, Seymour PD (1990) Graph minors IV. Tree width and well-quasi-ordering. J Comb Theory Ser B 48:227\u2013254","journal-title":"J Comb Theory Ser B"},{"key":"9141_CR18","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson N, Seymour PD (1986b) Graph minors V. Excluding a planar graph. J Comb Theory Ser B 41:92\u2013114","journal-title":"J Comb Theory Ser B"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-008-9141-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-008-9141-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-008-9141-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:12Z","timestamp":1559261892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-008-9141-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,13]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9141"],"URL":"https:\/\/doi.org\/10.1007\/s10878-008-9141-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,13]]}}}