A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes

DOI10.1145/1810959.1811005MaRDI QIDQ5405891zbMATH OpenOpenAlexFDO

Authors William T. Harvey, Yusu Wang, Rephael Wenger

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1810959.1811005

zbMATH Keywords

topologyrandomized algorithmsReeb graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A deterministic \(O(m \log m)\) time algorithm for the Reeb graph
• A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
• Efficient algorithms for computing Reeb graphs
• Note on an algorithm for computing the Reeb graph
• Reeb graphs: approximation and persistence
• Reeb graphs, approximation and persistence
• scientific article; zbMATH DE number 1263228
• Algorithms and complexity results for finding graphs with extremal Randić index
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Cited in

(20)

• Efficient Output-Sensitive Construction of Reeb Graphs
• Constructing Reeb graphs using cylinder maps
• Structure and stability of the one-dimensional Mapper
• Efficient algorithms for computing Reeb graphs
• Maintaining Reeb graphs of triangulated 2-manifolds
• Reeb graphs: approximation and persistence
• Robust computations of Reeb graphs in 2-D binary images
• Categorified Reeb graphs
• Realizable piecewise linear paths of persistence diagrams with Reeb graphs
• Gromov-Hausdorff approximation of filamentary structures using Reeb-type graphs
• Reeb graphs, approximation and persistence
• A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
• The JS-graphs of join and split trees (extended abstract)
• Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
• Avoiding the global sort: a faster contour tree algorithm
• Time-varying Reeb graphs for continuous space-time data
• Generalized persistence diagrams for persistence modules over posets
• Enhanced topology-sensitive clustering by Reeb graph shattering
• Time-varying Reeb graphs for continuous space-time data
• A deterministic \(O(m \log m)\) time algorithm for the Reeb graph

This page was built for publication: A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405891)