并行图论算法PDF电子书下载

第一章 并行计算机与并行计算模型 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