---
res:
bibo_abstract:
- "Let K be a simplicial complex and g the rank of its p-th homology group Hp(K)
defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and
annotate each p-simplex of K with a binary vector of length g with the following
property: the annotations, summed over all p-simplices in any p-cycle z, provide
the coordinate vector of the homology class [z] in the basis H. The basis and
the annotations for all simplices can be computed in O(n ω ) time, where n is
the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied
in O(n ω ) time. The precomputed annotations permit answering queries about the
independence or the triviality of p-cycles efficiently.\r\n\r\nUsing annotations
of edges in 2-complexes, we derive better algorithms for computing optimal basis
and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing
an optimal basis of H1(K) , we improve the previously known time complexity from
O(n 4) to O(n ω + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of
K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle
is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known
for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n
ω ) + 2 O(g) n 2logn time using annotations.\r\n@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Oleksiy
foaf_name: Busaryev, Oleksiy
foaf_surname: Busaryev
- foaf_Person:
foaf_givenName: Sergio
foaf_name: Cabello, Sergio
foaf_surname: Cabello
- foaf_Person:
foaf_givenName: Chao
foaf_name: Chen, Chao
foaf_surname: Chen
foaf_workInfoHomepage: http://www.librecat.org/personId=3E92416E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Tamal
foaf_name: Dey, Tamal
foaf_surname: Dey
- foaf_Person:
foaf_givenName: Yusu
foaf_name: Wang, Yusu
foaf_surname: Wang
bibo_doi: 10.1007/978-3-642-31155-0_17
bibo_volume: 7357
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Annotating simplices with a homology basis and its applications@
...