|
|||||
|
|
| 关于区间图的一些有效并行算法 | |
| 引用本文： | 唐策善,梁维发.关于区间图的一些有效并行算法[J].高校应用数学学报(A辑),1989,4(4):534-540. |
| 作者姓名： | 唐策善 梁维发 |
| 作者单位： | 中国科技大学计算机系 (唐策善)，中国科技大学计算机系(梁维发) |
| 摘 要： | 本文基于SIMD-CREW-PRAM一种可同时读但不可同时写的共享计算模型,给出了有关区间图的一些有效的并行算法。如找最大加权集团,最小集团覆盖,等权区间图的最大独立集及最小支配集,真区间图的哈密顿回路及最小带宽。所有这些算法都是最优的,其时间复杂性为O(logn)和处理器数为O(n)。 |
| 关 键 词： | 区间图 并行算法 最大加权集团 |
| 本文献已被 CNKI 维普 等数据库收录！ | |