A Fast Algorithm for Computing Zigzag Representatives
Algorithmica · 2026-06 · 88 (3)
DOI: 10.1007/s00453-026-01386-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 09.04.2026. Verfasst von Tamal K. Dey und 2 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation, U.S. Department of Energy.
Abstract (Originalsprache)
Zigzag filtrations of simplicial complexes generalize the usual filtrations by allowing simplex deletions in addition to simplex insertions. The barcodes computed from zigzag filtrations encode the evolution of homological features. Although one can locate a particular feature at any index in the filtration using existing algorithms, the resulting representatives may not be compatible with the zigzag: a representative cycle at one index may not map into a representative cycle at its neighbor. For this, one needs to compute compatible representative cycles along each bar in the barcode. It is known that the barcode for a zigzag filtration with m insertions and deletions can be computed in $$O(m^\omega )$$ O ( m ω ) time, where $$\omega < 2.373$$ ω < 2.373 is the matrix multiplication exponent. However, it is not known how to compute the compatible representatives so efficiently. For a non-zigzag filtration, the classical matrix-based algorithm provides representatives in $$O(m^3)$$ O ( m 3 ) time, which can be improved to $$O(m^\omega )$$ O ( m ω ) . However, no known algorithm for zigzag filtrations computes the representatives with the $$O(m^3)$$ O ( m 3 ) time bound. We present an $$O(m^2n)$$ O ( m 2 n ) time algorithm for this problem, where $$n\le m$$ n ≤ m is the size of the largest complex in the filtration.
Förderung
- National Science Foundation
- U.S. Department of Energy
Zitieren
APA
Dey, T. K., Hou, T., & Morozov, D. (2026). A Fast Algorithm for Computing Zigzag Representatives. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01386-4
Vancouver
Dey TK, Hou T, Morozov D. A Fast Algorithm for Computing Zigzag Representatives. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01386-4
BibTeX
@article{Dey2026,
author = {Dey, Tamal K. and Hou, Tao and Morozov, Dmitriy},
title = {A Fast Algorithm for Computing Zigzag Representatives},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {3},
doi = {10.1007/s00453-026-01386-4}
}
EUVIMED