• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Distributed Computing and Internet Technology >Parameterized Complexity of Defensive and Offensive Alliances in Graphs
【24h】

Parameterized Complexity of Defensive and Offensive Alliances in Graphs

机译：图中的防守和进攻联盟的参数化复杂性

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G = (V, E) and a subset S (∈) V(G), we denote by ds(v) the degree of a vertex v ∈ V in G[S], the subgraph of G induced by S. A non-empty set S (∈) V is a defensive alliance in G = (V, E) if ds(v)+1 ≥ ds~c(v) for all v ∈ S. A nonempty set S (∈) V is an offensive alliance in G if ds(v) ≥ ds~c(v) + 1 for all v ∈ N(S). It is known that the problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity by showing that (1) the problems are FPT when parameterized by neighbourhood diversity of the input graph, (2) the offensive alliance problem is FPT when parameterized by domino treewidth of the input graph, and (3) the defensive and offensive alliance problems are polynomial time solvable for graphs with bounded treewidth.
机译：在本文中，我们研究了一个简单的图表中寻找小型防守和进攻联盟的问题。 给定图G =（v，e）和子集s（∈）v（g），我们表示通过g [s]中的顶点V≠v的程度，由s引起的g的子图 。非空集S（∈）v是G =（v，e）的防御联盟，如果DS（v）+1≥ds〜c（v）为所有v∈s。一个非空的集合s（∈） v是g如果所有v∈n的gs（v）≥ds〜c（v）+ 1的令人反感的联盟。 众所周知，寻找小型防守和进攻联盟的问题是NP-Complete。 从参数化复杂性的角度来看，我们通过显示（1）通过输入图的邻域分集参数化的问题来提高对问题的理解，（2）当通过输入的Domino树宽的Domino Treewidth参数化时，FPT（2）令人反感的联盟问题是FPT 图表，（3）防御性和令人反感的联盟问题是具有有界树木宽度的图形的多项式时间可解决。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号