| 区间图上的并行算法设计 |
| |
| 引用本文： | 马军,刘振法. 区间图上的并行算法设计[J]. 山东大学学报(理学版), 1999, 34(4): 404-412 |
| |
| 作者姓名： | 马军 刘振法 |
| |
| 作者单位： | 1. 山东大学计算机系,济南250100
2. 中国电子进出口山东公司,济南250002 |
| |
| 基金项目： | 国家863306 、 |
| |
| 摘 要： | 对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.
|
| 关 键 词： | NP-难解 区间图 并行算法 |
| 修稿时间： | 1997-09-15 |
DESINGING EFFICIENT PARALLEL ALGORITHMS ON INTEVAL GRAPHS |
| |
| Ma Jun,Liu Zhenfa. DESINGING EFFICIENT PARALLEL ALGORITHMS ON INTEVAL GRAPHS[J]. Journal of Shandong University, 1999, 34(4): 404-412 |
| |
| Authors: | Ma Jun Liu Zhenfa |
| |
| Abstract: | Two ways in designing efficient parallel algorithms for interval graphs are discussed.They are used to develop the efficient parallel algorithms for following problems:Minimum Clique Cover,Maximum Clique,Maximum Independent Set,Minimum Dominating Set,Hamiltonian Circuit,Optimal Path Cover,Bandwidth Minimization and Steiner Tree.All given algorithms run in O (log n ) time with O(n ) processors on a EREW PRAM.Some of the sequential versions improve the time complexity of the best known sequential algorithms. |
| |
| Keywords: | NP Hard interval graphs parallel algorithms |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
