Scholarlink

Let \(G=(V, E)\) be a simple undirected graph with no isolated vertex. A set \(D_t\subseteq V\) is a total dominating set of G if (i) \(D_t\) is a dominating set, and (ii) the set \(D_t\) induces a subgraph with no isolated vertex. The total dominating set of the minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number ( \(\gamma _t(G)\) ). Given a graph G, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. In this paper, we enhance the hardness of the TDS problem by proving that it is NP-complete on grid-aligned UDGs, a subclass of unit disk graphs (UDGs). Furthermore, we present a 6.29 factor approximation algorithm for the TDS problem in UDGs.

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

Hardness and Approximation Results on the Total Dominating Set Problem

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Sasmita Rout,
  • Gautam Kumar Das

摘要

Let \(G=(V, E)\) be a simple undirected graph with no isolated vertex. A set \(D_t\subseteq V\) is a total dominating set of G if (i) \(D_t\) is a dominating set, and (ii) the set \(D_t\) induces a subgraph with no isolated vertex. The total dominating set of the minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number ( \(\gamma _t(G)\) ). Given a graph G, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. In this paper, we enhance the hardness of the TDS problem by proving that it is NP-complete on grid-aligned UDGs, a subclass of unit disk graphs (UDGs). Furthermore, we present a 6.29 factor approximation algorithm for the TDS problem in UDGs.