...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Graph-based data clustering with overlaps
【24h】

Graph-based data clustering with overlaps

机译：具有重叠的基于图的数据聚类

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number s. In the case of s-vertex-overlap, each vertex may be part of at most s maximal cliques; s-edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of "cluster graphs with overlaps", and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).
机译：我们介绍了重叠簇图修改问题，除了大多数以前的工作以外，目标图的簇可能会重叠。更准确地说，所研究的图问题要求最少数量的边修改，以使生成的图由可能重叠最多由重叠数s指定的特定数量的簇（即最大集团）组成。在s-vertex-overlap的情况下，每个顶点最多可能是s个最大派系的一部分; s-edge-overlap类似地在边缘方面定义。我们针对潜在的边缘修改问题提供了复杂性二分法（多项式时间可求解与NP-hard），开发了“具有重叠的集群图”的禁止子图表征，并根据允许的边缘修改次数研究了参数化的复杂性，从而实现了固定参数的可处理性（在s值恒定的情况下）和参数化的硬度（在s值无界的情况下）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号