买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜河南工业大学申请的专利基于割点分割机制的大规模图并行计算最大流的加速方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN110058945B 。

龙图腾网通过国家知识产权局官网在2025-04-11发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：201910322077.3，技术领域涉及：G06F9/50；该发明授权基于割点分割机制的大规模图并行计算最大流的加速方法是由张永新;魏蔚;张如青;邢征设计研发完成，并于2019-04-22向国家知识产权局提交的专利申请。

本基于割点分割机制的大规模图并行计算最大流的加速方法在说明书摘要公布了：本发明涉及基于割点分割机制的大规模图并行计算最大流的加速方法。关键步骤包括：1）构建大规模图的覆盖图；2）确定从源点到汇点在覆盖图上对应的唯一路径；3）将该路径上的顶点对应的子图全部提交到GraphChi平台进行并行最大流计算并整合子图最大流。本发明保证了每个子图最大流计算的独立性，减少了通讯次数，通过并行计算最大流再将结果整合，保证了其计算效率及正确性，能解决大规模图的最大流问题，显著提升求解最大流的计算速度。实验结果表明该方法能够充分利用问题本身特征，应对大规模图计算最大流的场景，相比经典算法能有效加速最大流的计算速度。

本发明授权基于割点分割机制的大规模图并行计算最大流的加速方法在权利要求书中公布了：1.基于割点分割机制的大规模图并行计算最大流的加速方法，其特征在于：在单机上处理大规模图，将对大规模图求解最大流的问题转化为了多个子图并行求解最大流的问题，基于割点分割机制构建覆盖图，覆盖图唯一路径上的顶点所对应的子图在并行GraphChi框架下快速求解；原大规模图构建覆盖图主要包括如下步骤：在算法的开始，遍历当前顶点的每一个邻居顶点，若邻居顶点未被访问，则值加1，将当前顶点与邻居顶点入栈；设置值为，随着顶点的不断遍历，值更新为通过非父亲顶点能够追溯到值最小的顶点；若邻居顶点已被访问且，则为割点并将映射到覆盖图中顶点；遍历到叶子结点后向上回溯，若栈顶元素不是当前正在访问的顶点或邻居顶点，则栈顶元素出栈并把栈顶元素顶点对中不是的顶点加入到覆盖图顶点映射的子图中，若栈顶元素为源点将当前覆盖图顶点设置为覆盖图的源点，若栈顶元素为汇点则将当前覆盖图顶点设置为覆盖图的汇点；若栈顶元素中有割点，则将该割点映射到覆盖图中，根据原图中割点之间的关系在覆盖图中顶点之间建立相应的联系，若栈顶元素为源点将当前覆盖图顶点设置为覆盖图的源点，若栈顶元素为汇点则将当前覆盖图顶点设置为覆盖图的汇点；给定的源点、汇点在找出在覆盖图上的唯一路径，具体实现方法如下：对于已经给出的源点，首先确定它所在的子图，并将该子图在覆盖图上对应的顶点标记为覆盖图的源点，同样的把汇点在覆盖图上对应的顶点标记为覆盖图的汇点；确定覆盖图上源点和汇点之后，从源点开始遍历所有路径直到到达汇点，因为通过割点分割机制构造的覆盖图是一个无向无环图，所以，从源点到汇点的路径只有唯一的一条；将覆盖图上这条从源点到汇点的路径上的所有顶点记录下来，根据这条唯一路径的方向，找出覆盖图上的这条路径的每个节点对应子图的源点、汇点；覆盖图唯一路径可转化为多子图并行求最大流问题，主要包括以下步骤：所述问题的目标公式表示为： 该公式所代表的含义是：每个子图的最大流等于源点到各出边点流量的最大值之和；限制条件为： 其中， ， 是唯一路径上顶点所对应的子图的集合 是第个子图 是第个子图的源点 是第个子图的汇点 表示每条边上容量 表示每条边上流量 是从顶点到顶点的流量 是从顶点到顶点的流量 是从顶点到顶点的流量 表示子图顶点出边的孩子节点集合 表示子图顶点入边的孩子节点集合 表示子图中所有边的集合 表示子图的顶点的取值是除源点、汇点之外的所有点的集合 表示子图顶点所有入边的集合，集合里的每一个顶点都属于顶点集，且顶点与顶点之间的边属于边集合 表示子图顶点所有出边点集合，集合里的每一个顶点都属于顶点集，且顶点与顶点之间的边属于边集合b.上述公式求得的是覆盖图路径上第子图的最大流，问题的解是并行求解覆盖图路径上各个子图的最大流，该路径上所有子图最大流的最小值对应原大规模图的最大流值，即： 表示覆盖图唯一路径上顶点的集合 表示覆盖图路径上的一个点，该点是原大规模图的一个子图表示子图里面的源点 表示子图里面的汇点c.公式②的含义是对唯一路径上所有的子图求最大流，并且取其中子图最大流的最小值，这个值就是整个覆盖图的最大流，也即是原大规模图的最大流。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人河南工业大学，其通讯地址为：450001 河南省郑州市高新技术产业开发区莲花街100号河南工业大学科技处；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。