Parameterized dominating set problem in chordal graphs: complexity and lower bound Export

@article{citeulike:4930929, abstract = {Abstract\ \ In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.}, author = {Liu, Chunmei and Song, Yinglei}, citeulike-article-id = {4930929}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s10878-008-9141-5}, citeulike-linkout-1 = {http://www.springerlink.com/content/x643540gk6100415}, day = {1}, doi = {10.1007/s10878-008-9141-5}, journal = {Journal of Combinatorial Optimization}, keywords = {algorithms, graph, parameterized}, month = {July}, number = {1}, pages = {87--97}, posted-at = {2009-06-23 07:28:05}, priority = {2}, title = {Parameterized dominating set problem in chordal graphs: complexity and lower bound}, url = {http://dx.doi.org/10.1007/s10878-008-9141-5}, volume = {18}, year = {2009} }

TY - JOUR ID - citeulike:4930929 L3 - citeulike-article-id:4930929 N2 - Abstract  In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph. IS - 1 JF - Journal of Combinatorial Optimization EP - 97 TI - Parameterized dominating set problem in chordal graphs: complexity and lower bound VL - 18 SP - 87 KW - algorithms KW - graph KW - parameterized AU - Liu, Chunmei AU - Song, Yinglei PY - 2009/07/01/ UR - http://dx.doi.org/10.1007/s10878-008-9141-5 ER -