Fast algorithms for minimum homology basis
This works describes three new randomized algorithms for calculating an optimal, i.e., a \textit{minimum} homology basis of the 1-dimensional homology group (given \(\mathbb{Z}_2\) coefficients). With all three algorithms have different computational complexities, the third one notably achieves nearly quadratic runtime in case the homology group has constant rank. This is result, while being of independent interest in computational topology, also lends itself to various applications like network analysis. Next to providing a detailed proof of the correctness and computational complexity of the described algorithms, the paper also contains pseudocode description of all algorithms as well as a discussion on how to implement the moist suitable algorithm in practice. This is complemented by an analysis of empirical performance on real-world and synthetic data, demonstrating the benefits of the proposed method.
- \textsc{Phat} -- persistent homology algorithms toolbox
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- A relaxed algorithm for online matrix inversion
- Annotating simplices with a homology basis and its applications
- Approximating loops in a shortest homology basis from point data
- Automata, Languages and Programming
- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Efficient algorithms for computing a minimal homology basis
- Fast matrix rank algorithms and applications
- Greedy optimal homotopy and homology generators
- Hardness results for homology localization
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 7760193 (Why is no real title available?)
- Linear independence oracles and applications to rectangular and low rank linear systems
- Measuring and computing natural generators for homology groups
- Minimum cycle and homology bases of surface-embedded graphs
- Minimum cycle bases, faster and simpler
- New approximation algorithms for minimum cycle bases of graphs
- PHAT -- persistent homology algorithms toolbox
- Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
- Simultaneous computation of the row and column rank profiles
- Solving sparse linear equations over finite fields
This page was built for publication: Fast algorithms for minimum homology basis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6963486)
