.png){kind=icon}
返回
Speeding-Up Graph Algorithms via Clique Partitioning
.png){kind=icon}
PRE
AI
DOI：10.1002/net.70038.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
减少图算法的运行时间对于解决大型图中的最短路径和匹配等现实问题至关重要，其中路径信息起着关键作用。为应对这一挑战，本文提出了一种图重构算法，该算法识别二部团并将其替换为三部图。这种重构在减少边数的同时保留了完整图的路径信息，使得匹配和所有对最短路径等算法能够直接应用，从而显著降低运行时间，尤其适用于大型稠密图。对于具有n个顶点和m条边的图G，所提出算法的运行时间为O(n^2 log n)，优于加速其他图算法的最佳现有算法（Feder-Motwani (FM)算法）的运行时间O(n^3)，其中n为顶点数。FM算法和所提出算法最初是为二部图设计的，但也可应用于一般有向或无向图。我们的广泛实验分析表明，所提出算法在边数减少方面最高可达21.26%，运行速度比FM算法最高快1.5倍。在包含最多10.5亿条边的合成图上，边数减少最高达74.36%。在真实图上，边数减少最高达46.8%。此外，作为预处理步骤使用时，该方法在大型合成图上为匹配算法带来最高2倍的加速，在真实图上为所有对最短路径算法带来最高1.5倍的加速，相较于直接使用给定图作为输入。
Keyword:
clique partitioning
graph algorithms
speeding-up graph algorithms
期刊
N
IF:
1.3
论文数:
50
被引数:
3.4K
机构
引用论文
.png){kind=icon}
Maximum Bipartite Matching in 𝑛
2+𝑜(1)
Time via a Combinatorial Algorithm通过组合算法在 𝑛2+𝑜(1) 时间内求解二分图最大匹配
PREAI
分享收藏分享收藏
查看更多内容