Name
Abstract | ||
|---|---|---|
We present a distributed algorithm to compute the first homology of a simplicial complex. Such algorithms are very useful in topological analysis of sensor networks, such as its coverage properties. We employ spanning trees to compute a basis for algebraic 1-cycles, and then use harmonics to efficiently identify the contractible and homologous cycles. The computational complexity of the algorithm is $O(|P|^\omega)$, where $|P|$ is much smaller than the number of edges, and $\omega$ is the complexity order of matrix multiplication. For geometric graphs, we show using simulations that $|P|$ is very close to the first Betti number. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Betti number,Algebraic number,Spanning tree,Topology,Discrete mathematics,Combinatorics,Algebra,Contractible space,Simplicial complex,Distributed algorithm,Matrix multiplication,Mathematics,Computational complexity theory |
DocType | Volume | Citations |
Journal | abs/1306.1158 | 0 |
PageRank | References | Authors |
0.34 | 19 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Harish Chintakunta | 1 | 36 | 6.05 |
| Hamid Krim | 2 | 520 | 59.69 |