w-Dominating Set Problem on Graphs of Bounded Treewidth

arXiv2101.02867MaRDI QIDQ6357816FDOQ6357816

Authors: Ke Liu, Mei Lu 

Publication date: 8 January 2021

Abstract: Let $G=(V,E)$ be a graph. Let $w$ be a positive integer. A $w$-dominating set is a vertex subset $S$ such that for all $vinV$, either $vinS$ or it has at least $w$ neighbors in $S$. The $w$-Dominating Set problem is to find the minimum $w$-dominating set. The $L$-Max $w$-Dominating Set problem is to find the vertex subset $S$ of cardinality at most $L$ that maximizes $|S|+|vinVsetminusS||N(v)capS|geqw|$, where $N(v)=u|uvinE$. In this paper, we give polynomial time algorithms to $w$-Dominating Set problem and $L$-Max $w$-Dominating Set problem on graphs of bounded treewidth.

This page was built for publication: $w$-Dominating Set Problem on Graphs of Bounded Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357816)