基于双连通分量覆盖图的稀疏大图最大流并行加速方法

刘扬; 魏蔚; 许贺洋

首页> 中文期刊> 《西北工业大学学报》 >基于双连通分量覆盖图的稀疏大图最大流并行加速方法

基于双连通分量覆盖图的稀疏大图最大流并行加速方法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

最大流问题是图论中重要的基础性问题,大规模网络中的最大流加速已成为重要研究方向,已有工作包括并行计算加速和图缩减加速2种思路,但仍有较大改进空间:(1)图缩减和并行计算2种加速思路并未充分融合,导致各自加速效果受限;(2)已有加速算法对常见的多次最大流求解支持不足,导致多次计算间存在大量冗余工作;(3)已有加速算法往往需涉及出入度和边容量等多个条件,计算复杂度偏高。针对上述问题,提出了一种基于优化子图的最大流并行加速方法,通过识别原始大图的双连通分量并建立覆盖图,可将任意最大流问题分解为独立的子问题,并行求解快速获取最大流精确解;覆盖图的构建仅涉及节点之间连接关系,具较低的时间复杂度。在基准图上的测试结果表明,算法可显著缩短稀疏大图中最大流计算时间。

著录项

来源
《西北工业大学学报》 |2018年第5期|955-962|共8页
作者
刘扬; 魏蔚; 许贺洋;
展开▼
作者单位

河南工业大学信息科学与工程学院;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
计算复杂度; 图理论; 最大流问题; 稀疏图计算; 双联通分量; 覆盖图; 并行计算;

相似文献

中文文献
外文文献
专利

1. 基于并行图计算框架大规模图最大流加速算法 [J] . 张如青 ,魏蔚 ,张永新 . 计算机仿真 . 2021,第002期
2. 图稀疏化:加速图聚类的有效方法 [J] . 温菊屏 ,林冬梅 . 计算机工程与设计 . 2013,第011期
3. 基于同构有向图的电网多场景仿真GPU批量并行加速方法 [J] . 宋炎侃 ,陈颖 ,于智同 . 电工电能新技术 . 2020,第003期
4. 基于卫星影像制作土地利用和土地覆盖图的方法试验——全国1∶5万土地利用/土地覆盖图制作试验项目 [J] . 王旭红 . 测绘通报 . 2001,第z1期
5. 基于并行计算的高效图稀疏化处理算法 [J] . 李融 . 四川理工学院学报（自然科学版） . 2015,第002期
6. 浅谈地表覆盖分类数据成果中地类属性错误大图斑问题的质量控制方法 [C] . 王程 ,成国立 ,王小平 . 广西测绘学会2018年学术交流会 . 2018
7. 基于图割算法的图像三维建模技术的并行加速研究与实现 [A] . 刘镁 . 2015

基于双连通分量覆盖图的稀疏大图最大流并行加速方法

摘要

著录项

相似文献

相关主题

期刊订阅