Parameterized dominating set problem in chordal graphs: complexity and lower bound期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

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

Authors:	Chunmei Liu Yinglei Song

Affiliation:	(1) Department of Systems and Computer Science, Howard University, Washington, DC 20059, USA;(2) Department of Mathematics and Computer Science, University of Maryland Eastern Shore, Princess Anne, MD 21853, USA

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 $\|V\|^{o({sqrt{k}})}$ unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to $O(2^{sqrt{k}}\|V\|^{2sqrt{k}})$ when the underlying graph G is an interval graph.

Keywords:	Chordal graphs Dominating set Parameterized complexity Lower bound Interval graphs
本文献已被 SpringerLink 等数据库收录！