• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
【24h】

Parallel algorithms for Hamiltonian problems on quasi-threshold graphs

机译：准阈值图上哈密顿问题的并行算法

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

摘要

In this paper we show structural and algorithmic properties on the class of quasi-threshold graphs, or QT-graphs for short, and prove necessary and sufficient conditions for a QT-graph to be Hamiltonian. Based on these properties and conditions, we construct an efficient parallel algorithm for finding a Hamiltonian cycle in a QT-graph; for an input graph on n vertices and m edges, our algorithm takes O(log n) time and requires O(n + m) processors on the CREW PRAM model. In addition, we show that the problem of recognizing whether a fir-graph is a Hamiltonian graph and the problem of computing the Hamiltonian completion number of a nonHamiltonian QT-graph can also be solved in O(log n) time with O(n + m) processors. Our algorithms rely on 0(log n)-time parallel algorithms, which we develop here, for constructing tree representations of a QT-graph; we show that a QT-graph G has a unique tree representation, that is, a tree structure which meets the structural properties of G. We also present parallel algorithms for other optimization problems on fir-graphs which run in O(log n) time using a linear number of processors.
机译：在本文中，我们在类准阈值图（简称QT图）上显示了结构和算法性质，并证明了将QT图成为哈密顿量的充要条件。基于这些特性和条件，我们构造了一种有效的并行算法，用于在QT图中查找哈密顿循环。对于n个顶点和m个边上的输入图，我们的算法需要O（log n）时间，并且在CREW PRAM模型上需要O（n + m）个处理器。此外，我们表明，还可以在O（log n）时间内使用O（n +）解决识别冷杉图是否是哈密顿图的问题以及计算非哈密顿QT图的哈密顿完成数的问题。 m）处理器。我们的算法依赖于此处开发的0（log n）-时间并行算法，用于构造QT图的树表示。我们表明QT图G具有唯一的树表示，即满足G的结构特性的树结构。我们还提出了针对O（log n）时间运行的图的其他优化问题的并行算法使用线性数量的处理器。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号