Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
复制标题
在无爪图中查找最长周期的精确算法
DOI：
10.1007/s00453-011-9576-4
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
Broersma H
中科院分区：
文献类型：
--
作者：
Broersma H
Hamilton圈问题是判定n-顶点图G是否有圈通过G的所有顶点的问题。该问题是一个经典的NP完全问题。找到一个精确的算法，解决它的时间为一些常数α<2是一个臭名昭著的开放问题，直到最近，当比约克隆德提出了一个随机算法，使用时间和多项式空间。最长圈问题是哈密尔顿圈问题的一个自然推广，它的任务是找到一个最长的圈。对于无爪图G，找到最长的循环等价于找到闭合的踪迹（即，连通偶子图，可能由单个顶点组成），支配某个关联图H的最大边数。使用这种翻译，我们得到两个确定性的算法，解决最长的周期问题，因此，汉密尔顿周期问题，无爪图：一个算法，使用时间和指数空间，和一个算法，使用时间和多项式空间。
TheHamiltonian Cycleproblem is the problem of deciding whether ann-vertex graphGhas a cycle passing through all vertices ofG. This problem is a classicNP-complete problem. Finding an exact algorithm that solves it intime for some constantα<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that usestime and polynomial space. TheLongest Cycleproblem, in which the task is to find a cycle of maximum length, is a natural generalization of theHamiltonian Cycleproblem. For a claw-free graphG, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graphH. Using this translation we obtain two deterministic algorithms that solve theLongest Cycleproblem, and consequently theHamiltonian Cycleproblem, for claw-free graphs: one algorithm that usestime and exponential space, and one algorithm that usestime and polynomial space.
登录
查看更多内容
计算无爪图中的尖锐 2 因子
DOI：
--
发表时间：
2008
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
H. Broersma;D. Paulusma
通讯作者：
D. Paulusma
DOI：
--
发表时间：
1977
期刊：
ACM Annual Conference
影响因子：
--
作者：
S. Kohn;A. Gottlieb;M. Kohn
通讯作者：
M. Kohn
DOI：
10.1016/0167-6377(82)90044-x
发表时间：
1982-04
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
R. Karp
通讯作者：
R. Karp
无爪图中哈密顿性的快速精确算法
DOI：
--
发表时间：
2009
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
H. Broersma;F. Fomin;P. Hof;D. Paulusma
通讯作者：
D. Paulusma
关于图的一些边划分问题的复杂性
影响因子：
1.1
作者：
Zbigniew Lonc
通讯作者：
Zbigniew Lonc