文章基本信息

标题：Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis
本地全文：下载
作者：Abhishek Rathod
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：64:1-64:11
DOI：10.4230/LIPIcs.SoCG.2020.64
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â"¤â,, 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. [Dey et al., 2018], runs in O(N^Ï + NÂ² 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Ìf(m^Ï) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^Ï + N m^{Ï-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Ìf(m^Ï) time.
关键词：Computational topology; Minimum homology basis; Minimum cycle basis; Simplicial complexes; Matrix computations