...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Finding large cycles in Hamiltonian graphs
【24h】

Finding large cycles in Hamiltonian graphs

机译：在哈密顿图中查找大周期

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

摘要

We show how to find in Hamiltonian graphs a cycle of length n(Omega)((1/loglogn)) = exp(Omega(log n/ log log n)) This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n(3)) time a cycle in G of length k(Omega(1/log d)) From this we infer that if G has a cycle of length k, then one can find in 0(n3) time a cycle of length k(Omega/(log(n/k)+log log n))), which implies the result for Hamiltonian graphs Our results improve, for some values of k and d, a recent result of Gabow (2004)1111 showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length exp(Omega(root log k/log log k)). We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f (g)k(Omega(1)), running in time O(n(2)) for planar graphs.
机译：我们展示了如何在哈密顿图中找到长度为n（Omega）（（1 / loglogn））= exp（Omega（log n / log log n））的循环。这是更普遍的结果的结果，其中我们证明：如果G的最大度数为d，并且具有一个包含k个顶点的周期（或者一个具有k个顶点的3个可循环次要H），那么我们可以在O（n（3））时间中找到一个长度为k（Omega（ 1 / log d））由此推断，如果G的周期为k，则可以在0（n3）的时间内找到一个周期为k（Omega /（log（n / k）+ log log n）的周期。 ）），这意味着汉密尔顿图的结果对于某些k和d值，我们的结果得到了Gabow（2004）1111的最新结果的改进，该结果表明，如果G的周期为k，则可以在多项式时间中找到a以长度exp（Omega（root log k / log log k））的G循环。我们最终证明，如果G具有固定的Euler属g，并且具有带有k个顶点的循环（或者具有k个顶点的3个可循环次要H），那么我们可以在多项式时间内找到长度为f（g）k（ Omega（1）），在平面图的时间O（n（2））中运行。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号