首页> 外文会议>Design and analysis of algorithms >Constant Thresholds Can Make Target Set Selection Tractable
【24h】

Constant Thresholds Can Make Target Set Selection Tractable

机译:恒定的阈值可使目标集选择变得可行

获取原文
获取原文并翻译 | 示例

摘要

Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful approximation as well as fixed-parameter algorithms. The task is to select a minimum number of vertices into a "target set" such that all other vertices will become active in course of a dynamic process (which may go through several activation rounds). A vertex, which is equipped with a threshold value t, becomes active once at least t of its neighbors are active; initially, only the target set vertices are active. We contribute further insights into islands of tractability for Target Set Selection by spotting new parameterizations characterizing some sparse graphs as well as some "cliquish" graphs and developing corresponding fixed-parameter tractability and (parameterized) hardness results. In particular, we demonstrate that upper-bounding the thresholds by a constant may significantly alleviate the search for efficiently solvable, but still meaningful special cases of Target Set Selection.
机译:目标集选择是社交网络分析和分布式计算中一个突出的NP问题,在实现有用的逼近和固定参数算法方面都非常困难。任务是在“目标集”中选择最少数量的顶点,以使所有其他顶点在动态过程(可能需要经过多个激活回合)的过程中变为活动状态。一旦至少t个邻居处于活动状态,则配备有阈值t的顶点将变为活动状态;最初,只有目标集顶点是活动的。我们通过发现表征某些稀疏图和一些“急速”图的新参数化并开发相应的固定参数可加工性和(参数化)硬度结果,为目标集选择的可加工性孤岛提供了进一步的见解。特别是,我们证明了将阈值上限提高一个常数可以显着减轻对目标集选择的有效可解决但仍然有意义的特殊情况的搜索。

著录项

  • 来源
    《Design and analysis of algorithms》|2012年|120-133|共14页
  • 会议地点 Kibbutz Ein Gedi(IL)
  • 作者单位

    LAMSADE, Universite Paris-Dauphine, France;

    Institut fuer Softwaretechnik und Theoretische Informatik, TU Berlin, Germany;

    Institut fuer Softwaretechnik und Theoretische Informatik, TU Berlin, Germany;

    Institut fuer Softwaretechnik und Theoretische Informatik, TU Berlin, Germany;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号