Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult

机译：次三次图中的哈密顿循环：是什么使问题变得困难

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We study the computational complexity of the hamiltonian CYCLE problem in the class of graphs of vertex degree at most 3. Our goal is to distinguish boundary properties of graphs that make the problem difficult (NP-complete) in this domain. In the present paper, we discover the first boundary class of graphs for the HAMILTONIAN CYCLE problem in subcubic graphs.

机译：我们最多在顶点度为3的图类中研究Hamilton CYCLE问题的计算复杂度。我们的目标是区分图的边界属性，这些图使该问题在该域中变得困难（NP完全）。在本文中，我们发现了亚三次图中哈密顿循环问题的图的第一类边界。

著录项

来源
《Theory and application of models of computation》|2010年|p.320-327|共8页
会议地点 Prague(CZ);Prague(CZ);Prague(CZ)
作者
Nicholas Korpelainen; Vadim V. Lozin; Alexander Tiskin;
展开▼
作者单位

DIMAP, University of Warwick, Coventry CV4 7AL, UK,Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK;

DIMAP, University of Warwick, Coventry CV4 7AL, UK,Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK;

DIMAP, University of Warwick, Coventry CV4 7AL, UK,Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词

相似文献

外文文献
中文文献
专利

1. Induced matchings in subcubic graphs without short cycles [J] . Michael A. Henning, Dieter Rautenbach Discrete mathematics . 2014,第Null期

机译：亚三次图中的诱导匹配而没有短周期
2. Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs [J] . Balogh Jozsef, Molla Theodore European journal of combinatorics . 2019,第期

机译：长彩虹周期和哈密顿循环在正确的边缘彩色的完整图表中使用许多颜色
3. Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs [J] . Jinfeng Feng Mathematical Methods of Operations Research . 2009,第2期

机译：无爪图中的哈密顿环和2主导的诱导环
4. Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult [C] . Nicholas Korpelainen, Vadim V. Lozin, Alexander Tiskin International Conference on Theory and Applications of Models of Computation . 2010

机译：汉密尔顿循环在子电机图中：是什么让问题变得困难
5. Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies. [D] . Nasab, Reza Zamani. 2011

机译：哈密顿量在二部图中的指定边，统治博弈以及革命者和间谍的博弈之间循环。
6. The odd-even invariant and Hamiltonian circuits in tope graphs [O] . Yvonne Kemper, Jim Lawrence -1

机译：拓扑图中的奇偶不变和哈密顿电路
7. Uniquely restricted matchings in subcubic graphs without short cycles [O] . M. Fürst, D. Rautenbach 2020

机译：在没有短期周期的子机图中的唯一限制匹配
8. Degree Sums, kappa-Factors and Hamiltonian Cycles in Graphs [R] . Faudree, R. J., van den Heuvel, J. 1992

机译：图中的度和，kappa因子和哈密顿环

Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult

摘要

著录项

相似文献

相关主题

期刊订阅