文章基本信息

标题：An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology
本地全文：下载
作者：Tamal K. Dey ; Tianqi Li ; Yusu Wang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：36:1-36:15
DOI：10.4230/LIPIcs.SoCG.2020.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and MÃ©moli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (Hâ,) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.
关键词：computational topology; directed graph; path homology; persistent path homology