License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.44
URN: urn:nbn:de:0030-drops-160525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16052/
Glisse, Marc ;
Pritam, Siddharth
Swap, Shift and Trim to Edge Collapse a Filtration
Abstract
Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit the use of edge collapse for efficient computation of persistent homology. We first give a simple and intuitive explanation of the principles underlying that algorithm. This in turn allows us to propose various extensions including a zigzag filtration simplification algorithm. We finally show some experiments to better understand how it behaves.
BibTeX - Entry
@InProceedings{glisse_et_al:LIPIcs.SoCG.2022.44,
author = {Glisse, Marc and Pritam, Siddharth},
title = {{Swap, Shift and Trim to Edge Collapse a Filtration}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {44:1--44:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16052},
URN = {urn:nbn:de:0030-drops-160525},
doi = {10.4230/LIPIcs.SoCG.2022.44},
annote = {Keywords: edge collapse, flag complex, graph, persistent homology}
}
