Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis
复制标题
最小循环基础和最小同源基础的快速算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Abhishek Rathod
中科院分区：
文献类型：
--
作者：
Abhishek Rathod
本文研究了在给定的单纯复形K中求最小同调基的问题，即求一个最短的圈集，它能生成系数为Z2的1维同调类.这个问题在过去几年中得到了广泛的研究。对于一般的复形，目前最好的确定性算法，由Dey等人[8]，运行时间为O（N ω + N 2 g），其中N表示K中单形的个数，g表示K的1-同调群的秩，ω表示矩阵乘法的指数。在本文中，我们提出了两个概念上简单的随机算法，计算一般单纯复形K的最小同调基。第一个算法运行时间为O（m ω），其中m表示K中的边数，而第二个算法运行时间为O（m ω + Nm ω − 1）。我们还研究了在n个顶点m条边的无向图G中求最小圈基的问题。这个问题的最佳算法运行时间为O（m ω）。我们的算法，它有一个更简单的高级描述，但稍微更昂贵，运行时间为n = O（m ω）。
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with Z 2 coefficients in a given simplicial complex K . This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. [8], runs in O ( N ω + N 2 g ) time, where N denotes the number of simplices in K , g denotes the rank of the 1-homology group of K , and ω denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K . The first algorithm runs in ˜ O ( m ω ) time, where m denotes the number of edges in K , whereas the second algorithm runs in O ( m ω + Nm ω − 1 ) time. We also study the problem of finding a minimum cycle basis in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O ( m ω ) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in ˜ O ( m ω ) time.