{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:21Z","timestamp":1759063821419},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,4,15]],"date-time":"2010-04-15T00:00:00Z","timestamp":1271289600000},"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":[[2011,11]]},"DOI":"10.1007\/s10878-010-9317-7","type":"journal-article","created":{"date-parts":[[2010,4,14]],"date-time":"2010-04-14T20:36:15Z","timestamp":1271277375000},"page":"684-698","source":"Crossref","is-referenced-by-count":11,"title":["Parameterized complexity and inapproximability of\u00a0dominating set problem in chordal and near chordal graphs"],"prefix":"10.1007","volume":"22","author":[{"given":"Chunmei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Yinglei","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,15]]},"reference":[{"issue":"3","key":"9317_CR1","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\u00a0ACM 51(3):363\u2013384","journal-title":"J\u00a0ACM"},{"issue":"1","key":"9317_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J\u00a0ACM 41(1):153\u2013180","journal-title":"J\u00a0ACM"},{"key":"9317_CR3","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen J, Kanj IA, Jia W (2001) Vertex cover: further observations and further improvements. J\u00a0Algorithms 41:280\u2013301","journal-title":"J\u00a0Algorithms"},{"key":"9317_CR4","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 thirty-sixth ACM symposium on theory of computing (STOC 2004), pp\u00a0212\u2013221","DOI":"10.1145\/1007352.1007391"},{"issue":"4","key":"9317_CR5","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J Chen","year":"2007","unstructured":"Chen J, Fernau H, Kanj IA, Xia G (2007) Parametric duality and lower bounds and upper bounds on Kernel size. SIAM J Comput 37(4):1077\u20131106","journal-title":"SIAM J Comput"},{"key":"9317_CR6","series-title":"LNCS","first-page":"192","volume-title":"Proceedings of 12th annual European symposium on algorithms","author":"M Chleb\u00edk","year":"2004","unstructured":"Chleb\u00edk M, Chleb\u00edkova J (2004) Approximation hardness of dominating set problems. In: Proceedings of 12th annual European symposium on algorithms. LNCS, vol\u00a03221. Springer, Berlin, pp\u00a0192\u2013203"},{"key":"9317_CR7","doi-asserted-by":"crossref","unstructured":"Dinur I, Safra S (2002) The importance of being biased. In: Proceeding of the thirty-fourth ACM symposium on theory of computing (STOC 2002), pp\u00a033\u201342","DOI":"10.1145\/509907.509915"},{"key":"9317_CR8","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed parameter tractability and completeness i: basic theory. SIAM J Comput 24:873\u2013921","journal-title":"SIAM J Comput"},{"key":"9317_CR9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1998","unstructured":"Downey RG, Fellows MR (1998) Parameterized complexity. Springer, Berlin"},{"key":"9317_CR10","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"G Fanica","year":"1974","unstructured":"Fanica G (1974) The intersection graphs of subtrees in trees are exactly the chordal graphs. J\u00a0Comb Theory, Ser B 16:47\u201356","journal-title":"J\u00a0Comb Theory, Ser B"},{"key":"9317_CR11","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"1","author":"M Farber","year":"1982","unstructured":"Farber M (1982) Independent domination in chordal graphs. Oper Res Lett 1:134\u2013138","journal-title":"Oper Res Lett"},{"key":"9317_CR12","series-title":"Series of books in the mathematical sciences","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. Series of books in the mathematical sciences. Freeman, New York. A\u00a0guide to the theory of NP-completeness"},{"issue":"2","key":"9317_CR13","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"I","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica I(2):169\u2013197","journal-title":"Combinatorica"},{"key":"9317_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rson","year":"1993","unstructured":"Halld\u00f3rson MM (1993) Approximating the minimum maximal independence number. Inf Process Lett 46:169\u2013172","journal-title":"Inf Process Lett"},{"key":"9317_CR15","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximate algorithms for combinatorial problems. J\u00a0Comput Syst Sci 9:256\u2013278","journal-title":"J\u00a0Comput Syst Sci"},{"issue":"1","key":"9317_CR16","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s10878-008-9141-5","volume":"18","author":"C Liu","year":"2009","unstructured":"Liu C, Song Y (2009) Parameterized dominating set problem in chordal graphs: complexity and lower bound. J\u00a0Comb Optim 18(1):87\u201397","journal-title":"J\u00a0Comb Optim"},{"key":"9317_CR17","doi-asserted-by":"crossref","unstructured":"Lokshtanov D, Mnich M, Saurabh S (2009) Linear Kernel for planar connected dominating set. In: Proceedings of the sixth annual conference on theory and applications of models of computation (TAMC 2009), pp\u00a0281\u2013290","DOI":"10.1007\/978-3-642-02017-9_31"},{"issue":"8\u201310","key":"9317_CR18","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1016\/j.tcs.2008.11.023","volume":"410","author":"YL Orlovich","year":"2009","unstructured":"Orlovich YL, Gordon VS, de Werra D (2009) On the inapproximability of independent domination in 2P 3-free perfect graphs. Theor Comput Sci 410(8\u201310):977\u2013982","journal-title":"Theor Comput Sci"},{"key":"9317_CR19","doi-asserted-by":"crossref","unstructured":"Raz R, Safra S (1997) A\u00a0sub-constant error-probability low degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the twenty-ninth ACM symposium on theory of computing (STOC 1997), pp\u00a0475\u2013484","DOI":"10.1145\/258533.258641"},{"issue":"8","key":"9317_CR20","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1109\/TPDS.2006.103","volume":"17","author":"S Yang","year":"2006","unstructured":"Yang S, Wu J, Cardei M, Dai F (2006) Extended dominating set and its applications in ad hoc networks using cooperative communication. IEEE Trans Parallel Distrib Comput 17(8):851\u2013864","journal-title":"IEEE Trans Parallel Distrib Comput"},{"key":"9317_CR21","doi-asserted-by":"crossref","unstructured":"Zhu J (2009) Approximation for minimum dominating set. In: Proceedings of the 2nd international conference on interaction sciences: information technology, culture and human, pp\u00a0119\u2013124","DOI":"10.1145\/1655925.1655948"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9317-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-010-9317-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9317-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:16Z","timestamp":1559276296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-010-9317-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,15]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9317"],"URL":"https:\/\/doi.org\/10.1007\/s10878-010-9317-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,15]]}}}