INCLUSION AND EXCLUSION ALGORITHM FOR THE HAMILTONIAN PATH PROBLEM

被引：38

作者：

BAX, ET

机构：

[1] Department of Computer Science, Furman University, Greenville

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 47卷 / 04期

关键词：

COMBINATORIAL PROBLEMS; HAMILTONIAN PATH PROBLEM; NP PROBLEMS; GRAPH THEORY;

D O I：

10.1016/0020-0190(93)90033-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper contains a description of an algorithm that uses the principle of inclusion and exclusion to determine the number of Hamiltonian paths in a given graph that have a given starting vertex and a given ending vertex, and it also contains a description of a similar algorithm to determine the number of Hamiltonian cycles in a given graph. The algorithms have an upper bound on time complexity of O(2n x n4) where n is the number of vertices in the graph. Also, the algorithms require only O(n3 log2 n) bits of storage space.

引用

页码：203 / 207

页数：5