THE HAMILTON CIRCUIT PROBLEM ON GRIDS

被引：10

作者：

AFRATI, F

机构：

来源：

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 1994年 / 28卷 / 06期

关键词：

D O I：

10.1051/ita/1994280605671

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper investigates the Hamilton circuit problem on grid graphs. For general grid graphs it is known to be NP-complete. We consider a non-trivial subclass of grid graphs and present a linear algorithm for finding a Hamilton circuit. Moreover, we show that our algorithm can be optimally parallelized, hence the problem belongs to NC.

引用

页码：567 / 582

页数：16

共 11 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER
[2] FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS
ANGLUIN, D
VALIANT, LG
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) : 155 - 193
[3] Berge C., 1973, GRAPHS HYPERGRAPHS
[4] Bollobas B., 1978, LONDON MATH SOC MONO
[5] Dahlhaus E., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P186, DOI 10.1109/SFCS.1988.21936
[6] PARALLEL ALGORITHMS FOR FINDING HAMILTON CYCLES IN RANDOM GRAPHS
FRIEZE, AM
[J]. INFORMATION PROCESSING LETTERS, 1987, 25 (02) : 111 - 117
[7] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[8] HAMILTON PATHS IN GRID GRAPHS
ITAI, A
PAPADIMITRIOU, CH
SZWARCFITER, JL
[J]. SIAM JOURNAL ON COMPUTING, 1982, 11 (04) : 676 - 686
[9] KARP RM, 1988, CSD88408 UCB TECHN R
[10] SILVESTER J, 1983, AUG IEEE T COMM, P974

← 1 2 →