第一章 并行计算机与并行计算模型 1
1.1 并行计算机及其分类 1
1.1.1 并行计算机介绍 2
1.1.2 并行计算机分类 4
1.2 并行计算模型 4
1.2.1 SIMD共享存贮模型 6
1.2.2 SIMD互连网络模型 7
1.2.3 MIMD并行计算模型 13
1.3 小结 14
参考文献 14
第二章 并行算法的度量与设计技术 16
2.1 并行算法的基本概念 16
2.2 MIMD机器上的算法 16
2.3 并行算法的度量标准 17
2.3.1 算法复杂性的基本概念 17
2.3.2 并行算法的复杂性度量 18
2.3.3 并行算法的性能评价 19
2.4 并行算法的表示及约定 20
2.5 并行算法的设计技术 21
2.5.1 几种基本的设计技术 21
2.5.2 设计并行算法应注意的几个问题 24
2.6 小结 25
参考文献 25
第三章 图的搜索 27
3.1 图的并行搜索 27
3.1.1 算法的基本原理 27
3.1.2 p-深度优先搜索 27
3.1.3 p-宽深优先搜索 28
3.1.4 p-宽度优先搜索 28
3.2 图的分布式搜索 30
3.2.1 纯遍历搜索算法 30
3.2.2 深度优先搜索算法 31
3.2.3 改进的深度优先搜索算法 33
3.2.4 宽度优先搜索算法 35
3.2.5 改进的宽度优先搜索算法 37
3.3 小结 41
参考文献 42
第四章 求连通分支的并行算法 43
4.1 传递闭包法 43
4.2 顶点倒塌法 46
4.2.1 算法的基本原理 46
4.2.2 算法的形式化描述 46
4.2.3 算法的正确性证明 47
4.2.4 算法的复杂性分析 49
4.3 最优的连通分支算法 51
4.4 稀疏图的连通分支算法 54
4.5 一维阵列上的连通分支算法 54
4.6 二维网孔上的连通分支算法 56
4.7 小结 59
参考文献 61
第五章 最小生成树的并行算法 63
5.1 Sollin算法的并行化 63
5.2 树机上的MST算法 65
5.3 二维网孔上的MST算法 68
5.3.1 算法的基本原理 68
5.3.2 算法的非形式化描述 68
5.3.3 算法的复杂性分析 71
5.4 MST的更新算法 71
5.4.1 基本概念 71
5.4.2 顶点更新的MST算法 74
5.4.3 边更新的MST算法 75
5.5 MIMD共享存贮模型上的MST算法 77
5.6 分布式MST算法 78
5.6.1 算法的基本原理 79
5.6.2 算法的非形式化描述 79
5.6.3 算法的复杂性分析及正确性证明 81
5.6.4 其它改进的分布式MST算法 82
5.7 小结 82
参考文献 84
第六章 最短路径的并行算法 87
6.1 单源最短路径算法 87
6.2 所有顶点对的最短路径算法 89
6.3 二维网孔上的最短路径算法 91
6.4 MIMD共享存贮模型上的最短路径算法 92
6.4.1 算法的基本原理 93
6.4.2 算法的形式化描述 94
6.5 分布式单源最短路径算法 98
6.5.1 算法的基本原理 98
6.5.2 算法的形式化描述 99
6.5.3 算法的正确性证明 101
6.6 小结 102
参考文献 104
第七章 矩阵乘法及其在图论算法中的应用 106
7.1 矩阵乘法的一个简单并行算法 106
7.2 二维网孔上矩阵乘法的下界 107
7.3 二维网孔上的矩阵乘法算法 108
7.4 超立方上的矩阵乘法算法 109
7.5 洗牌网络上的矩阵乘法算法 112
7.6 MIMD共享存模型上的矩阵乘法算法 114
7.7 矩阵乘法在图论算法中的应用 117
7.7.1 计算图的传递闭包 117
7.7.2 计算所有顶点对的最短路径 117
7.7.3 计算图的中值和中值长度 118
7.8 小结 119
参考文献 120
第八章 基本回路、关节点、双连通分支和桥的并行算法 121
8.1 逆树的一些基本性质 121
8.2 找图的基本回路算法 122
8.3 找图的双连通分支算法 124
8.3.1 算法的基本原理 124
8.3.2 算法的非形式化描述 128
8.4 用欧拉遍历技术求双连通分支算法 130
8.4.1 算法的基本原理 130
8.4.2 算法的非形式化描述 130
8.4.3 算法在SIMD共享存贮模型上的实现 133
8.5 桥的算法 137
8.5.1 桥的基本性质 137
8.5.2 算法的非形式化描述 138
8.5.3 二维网孔上的桥算法 139
8.6 双连通分支算法的应用——求图的关节点 141
8.7 小结 142
参考文献 142
第九章 欧拉图及哈密顿图的并行算法 144
9.1 找欧拉回路的算法 144
9.1.1 欧拉图的基本概念及性质 144
9.1.2 找有向欧拉回路的算法 145
9.2 在竞赛图中找哈密顿回路算法 151
9.2.1 竞赛图的一些基本性质 151
9.2.2 算法的基本原理 153
9.2.3 算法的形式化描述 157
9.2.4 算法的复杂性分析 158
9.3 小结 159
参考文献 159
第十章 流图的并行算法 161
10.1 共享存贮模型上的AOE网问题的并行算法 161
10.1.1 AOE网的存在性测试算法 161
10.1.2 AOE网的拓扑排序算法 162
10.1.3 AOE网的关键路径算法 165
10.2 超立方和洗牌网络上的AOE网算法 170
10.2.1 超立方和洗牌网络上的拓扑排序算法 170
10.2.2 超立方和洗牌网络上的关键路径算法 172
10.3 AOE网的分布式算法 173
10.3.1 算法的形式化描述 174
10.3.2 算法的正确性证明 176
10.4 最大流问题的并行算法 177
10.4.1 有向流网络的基本概念 177
10.4.2 最大流并行算法的高层描述 178
10.4.3 PS-树及其上的操作 181
10.4.4 最大流算法的并行实现 183
10.4.5 最大流算法的有效实现 187
10.4.6 算法的复杂性分析 188
10.5 最大流问题的分布式算法 190
10.5.1 最大流问题的一些基本概念 190
10.5.2 深度优先搜索的最大流问题的分布式算法 191
10.6 小结 193
参考文献 194
第十一章 极大独立集的并行算法 195
11.1 引言 195
11.2 概率算法的基本概念 195
11.3 极大独立集问题的简单并行算法 197
11.3.1 极大独立集问题的基本知识 197
11.3.2 极大独立集问题并行算法的高层描述 198
11.3.3 极大独立集问题的随机并行算法 199
11.3.4 随机并行算法的复杂性分析 201
11.3.5 极大独立集问题的并行确定性算法 204
11.4 有效的极大独立集并行算法 210
11.4.1 基本概念 210
11.4.2 算法的形式化描述 211
11.4.3 算法的复杂性分析 218
11.5 小结 219
参考文献 220
第十二章 图着色的并行算法 221
12.1 图的顶点着色的并行算法 221
12.1.1 常数度图的着色算法 221
12.1.2 常数度图着色算法的应用 223
12.1.3 平面图5-着色并行算法 225
12.1.4 平面图5-着色最优的并行算法 229
12.2 图的边着色的并行算法 235
12.2.1 树的边着色并行算法 235
12.2.2 d-路图和d-路二分图的基本概念 236
12.2.3 2-路图的边着色并行算法 237
12.2.4 二次幂d-路二分图边着色的并行算法 239
12.2.5 正整数d-路二分图边着色的并行算法 241
12.2.6 多重图边着色的并行算法 244
12.3 小结 245
参考文献 246
第十三章 组合搜索 247
13.1 分治法 248
13.1.1 SIMD模型的分治算法 248
13.1.2 分治法在MIMD上的实现途径 249
13.1.3 分治算法的复杂性 249
13.2 分枝限界法 251
13.2.1 8-谜问题-一个例子 251
13.2.2 分枝限界方法 253
13.2.3 旅行商问题 255
13.2.4 并行分枝限界算法的异常情况 259
13.3 α-β搜索 261
13.3.1 α-β算法 262
13.3.2 改进的α-β搜索 264
13.3.3 并行搜索算法 265
13.4 小结 269
参考文献 272
第十四章 神经网络在图论问题中的应用 274
14.1 概述 274
14.1.1 生物神经元模型 274
14.1.2 神经网络的基本特征 275
14.2 Hopfield模型和旅行商问题 279
14.2.1 引言 279
14.2.2 Hopfield模型简介 280
14.2.3 HT模型下的旅行商问题 282
14.2.4 HT模型的改进 284
14.3 其它模型和旅行商问题 286
14.3.1 弹性网法 286
14.3.2 自组织映射 288
14.3.3 模拟退火 291
14.3.4 均场退火 293
14.4 应用举例 297
14.5 小结 307
参考文献 307
算法索引 309