details: High-Performance and Scalable GPU Graph Traversal我读的这篇详细的 BFS approach componentsContract-Expand Two-Phase gatheringCoarse-Grained, Warp-Based Gathering Fine-Grained, Scan-Based Gathering...

GraphChi: Large-Scale Graph Computation on Just a PC | USENIX2012 OSDI Parallel Sliding Windows (PSW) 关键：以interval为单元的BSP(Bulk-Synchronous Parallel)；设计存储layout，使得获取一个interval中所有顶点的邻居只需要 顺序 访问全图磁盘...

MSBFSThe More the Merrier: Efficient Multi-Source Graph TraversalVLDB 2014 基准 bit op ANP（这个） tuningcache line heuristic maximum sharing way of grouping BFSs reason:

定义bij：顶点Ni到顶点Nj间边Bij的容量fij：顶点Ni到顶点Nj的最大流流量F是fij构成的方阵 贡献判定一个F是否能在某些网络拓扑中达到 判定算法：求fij；然后在构造最大生成树时检查是否违反这个 (1)可以自然推出：>=i-p任意“路径”（注意路径上“相邻”两点不需要有边相连）的minflow 证明过程中提出：以fij作为边Bij的权重构造一棵最大生成树，对于...

defintions unit network单位网络：每个顶点要么只有一条出边且容量为1，要么只有一条入边且容量为1 unit capacity network单位容量网络：所有边容量=1 reductions of problem versionundirected->directed https://stackoverflow.com/questions/297416...

思考目前没有看完，刚看完central path的定义，在看norm的定义，浏览了下算法overall，似乎文章主要目标在max-flow的max，augment path的步骤文章中是直接说执行这个步骤，即这个步骤和往昔的max-flow算法是一样的，而++max-flow的disjoint是cancel flow提供的++，通过augment path步骤构造路径，而我们只需要两条aug...