• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
【24h】

Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width

机译：开发有限的线性结构以适应集团宽度的硬度

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

摘要

Clique-width is an important graph parameter whose computation is NP-hard. In fact we do not know of any algorithm other than brute force for the exact computation of clique-width on any graph class of unbounded clique-width, other than square grids. Results so far indicate that proper interval graphs constitute the first interesting graph class on which we might have hope to compute clique-width, or at least its variant linear clique-width, in polynomial time. In TAMC 2009, a polynomial-time algorithm for computing linear clique-width on a subclass of proper interval graphs was given. In this paper, we present a polynomial-time algorithm for a larger subclass of proper interval graphs that approximates the clique-width within an additive factor 3. Previously known upper bounds on clique-width result in arbitrarily large difference from the actual clique-width when applied on this class. Our results contribute toward the goal of eventually obtaining a polynomial-time exact algorithm for clique-width on proper interval graphs.
机译：集团宽度是一个重要的图形参数，其计算是NP难的。实际上，除了蛮力之外，我们不知道任何算法可以精确计算方格宽度的任何图类上的方格宽度，方格除外。到目前为止的结果表明，适当的间隔图构成了第一个有趣的图类，我们可能希望在该类上以多项式时间计算群宽度，或者至少是其变体线性群宽度。在TAMC 2009中，给出了用于在适当间隔图的子类上计算线性集团宽度的多项式时间算法。在本文中，我们针对适当间隔图的较大子类提出了多项式时间算法，该算法在加性因子3内近似了集团宽度。先前已知的集团宽度上限导致与实际集团宽度任意大的差异当应用于此类时。我们的结果有助于最终获得适当间隔图上的集团宽度的多项式时间精确算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号