• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs
【24h】

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

机译：无爪图中汉密尔顿性的快速精确算法

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

摘要

The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in (O)*(an) time for some constant α < 2 is a notorious open problem. For a claw-free graph G, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph H. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses 0*(1.6818n) time and exponential space, and one algorithm that uses 0*(1.8878n) time and polynomial space.
机译：哈密​​顿循环问题询问一个n顶点图G是否具有一个穿过G的所有顶点的循环。该问题是经典的NP完全问题。到目前为止，找到一个精确的算法可以在（O）*（an）时间内解决某个常数α<2的问题，这是一个臭名昭著的开放问题。对于无爪图G，找到一个哈密顿环等效于找到一个闭合轨迹（欧拉子图），该轨迹占主导地位的相关图H的边缘。使用这种转换，我们获得了两种精确的算法来解决该类的哈密顿环问题无爪图的一种：一种使用0 *（1.6818n）时间和指数空间的算法，另一种使用0 *（1.8878n）时间和多项式空间的算法。

著录项

  • 来源
  • 会议地点 Montpellier(FR);Montpellier(FR)
  • 作者

    Hajo Broersma; Fedor V. Fomin; Pirn van t Hof; Daniel Paulusma;

  • 作者单位

    Department of Computer Science, University of Durham,Science Laboratories, South Road, Durham DH1 3LE, England;

    Institutt for informatikk, Universitet i Bergen,Postboks 7803, 5020 Bergen, Norway;

    Department of Computer Science, University of Durham,Science Laboratories, South Road, Durham DH1 3LE, England;

    Department of Computer Science, University of Durham,Science Laboratories, South Road, Durham DH1 3LE, England;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机网络;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号