Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Milosavljevic, Nikola Morozov, Dmitriy Skraba, Primoz dblp dblp dblp Not MPG Author(s): Morozov, Dmitriy Skraba, Primoz
 Editor(s):
 BibTeX cite key*: Milosavljevic2011Zigzag

 Title, Booktitle
 Title*: Zigzag Persistent Homology in Matrix Multiplication Time Booktitle*: Proceedings of the 27th Annual Symposium on Computational Geometry (SCG'11)

 Event, URLs
 URL of the conference: http://socg2011.inria.fr/ URL for downloading the paper: http://doi.acm.org/10.1145/1998196.1998229 Event Address*: Paris, France Language: English Event Date* (no longer used): Organization: Event Start Date: 13 June 2011 Event End Date: 15 June 2011

 Publisher
 Name*: ACM URL: Address*: New York, NY Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 216-225 Year*: 2011 VG Wort Pages: ISBN/ISSN: 978-1-4503-0682-9 Sequence Number: DOI: 10.1145/1998196.1998229

 (LaTeX) Abstract: We present a new algorithm for computing zigzag persistent homology, an algebraic structure which encodes changes to homology groups of a simplicial complex over a sequence of simplex additions and deletions. Provided that there is an algorithm that multiplies two $n \times n$ matrices in $M(n)$ time, our algorithm runs in $O(M(n) + n^2 \log^2 n)$ time for a sequence of $n$ additions and deletions. In particular, the running time is $O(n^{2.376})$, by result of Coppersmith and Winograd. The fastest previously known algorithm for this problem takes $O(n^3)$ time in the worst case. Keywords: Zigzag persistent homology, matrix multiplication. Copyright Message: Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2011 ACM 978-1-4503-0682-9/11/06 ....\$10.00. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Milosavljevic2011Zigzag,
AUTHOR = {Milosavljevic, Nikola and Morozov, Dmitriy and Skraba, Primoz},
TITLE = {Zigzag Persistent Homology in Matrix Multiplication Time},
BOOKTITLE = {Proceedings of the 27th Annual Symposium on Computational Geometry (SCG'11)},
PUBLISHER = {ACM},
YEAR = {2011},
PAGES = {216--225},