Scholarlink

In this paper, we study a variant of Domination called Minimum Membership Dominating Set, in short MMDS. The input to the problem is a graph G and an integer k (which is the membership parameter). The goal is to compute a set \(S\subseteq V(G)\) such that for each \(v\in V(G)\) , \(1\le |N[v]\cap S|\le k\) . Notice that there is no requirement on the size of S. We extend the study on this problem from the parameterized complexity perspective. The following are the results of this paper.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Complexity of Minimum Membership Dominating Set

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • D. Karthika,
  • R. Muthucumaraswamy,
  • Matthias Bentert,
  • Sriram Bhyravarapu,
  • Saket Saurabh,
  • Sanjay Seetharaman

摘要

In this paper, we study a variant of Domination called Minimum Membership Dominating Set, in short MMDS. The input to the problem is a graph G and an integer k (which is the membership parameter). The goal is to compute a set \(S\subseteq V(G)\) such that for each \(v\in V(G)\) , \(1\le |N[v]\cap S|\le k\) . Notice that there is no requirement on the size of S. We extend the study on this problem from the parameterized complexity perspective. The following are the results of this paper.