《并行图论算法》求取 ⇩

第一章并行计算机与并行计算模型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.4MST的更新算法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.4MIMD共享存贮模型上的最短路径算法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.3AOE网的分布式算法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.2Hopfield模型和旅行商问题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