Partitioning graphs into Hamiltonian ones

被引：15

作者：

Chen, L

机构：

[1] UNIV CALIF LOS ANGELES,LOS ANGELES,CA 90024

[2] UNIV SO CALIF,LOS ANGELES,CA 90089

来源：

PARALLEL COMPUTING | 1996年 / 22卷 / 04期

关键词：

parallel algorithms; graph partition; Hamiltonian graphs; bipartite permutation graphs; time and processor requirements;

D O I：

10.1016/0167-8191(95)00007-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

In this paper, we present an (optimal) linear-time algorithm that decides whether a bipartite permutation graph can be partitioned into one or more induced Hamiltonian subgraphs each of which contains at least k vertices for a given k, and if so, obtains such a partition. We then give an efficient parallelization of the algorithm. We also investigate the problem of partitioning arbitrary directed graphs into Hamiltonian ones.

引用

页码：607 / 618

页数：12

共 21 条

[1]

ON THE PHYSICAL DESIGN OF PRAMS [J].