A deterministic O(m m) time algorithm for the Reeb graph

DOI10.1007/S00454-013-9511-3MaRDI QIDQ2391712zbMATH OpenOpenAlexFDO

Authors Salman Parsa

Publication date 5 August 2013

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-013-9511-3

zbMATH Keywords

algorithmsReeb graphgraph connectivityPL topology

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• A deterministic \(O(m \log m)\) time algorithm for the Reeb graph
• A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
• Efficient algorithms for computing Reeb graphs
• Note on an algorithm for computing the Reeb graph
• Reeb graphs: approximation and persistence

Cites work

• A data structure for dynamic trees
• A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
• Computing contour trees in all dimensions
• Dynamic trees in practice
• Dynamizing static algorithms, with applications to dynamic trees and history independence
• Efficient algorithms for computing Reeb graphs
• Logarithmic Lower Bounds in the Cell-Probe Model
• Loops in Reeb graphs of 2-manifolds
• Maintaining information in fully dynamic trees with top trees
• Near-optimal fully-dynamic graph connectivity
• Offline Algorithms for Dynamic Minimum Spanning Tree Problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Reeb graphs for shape analysis and applications
• Reeb graphs, approximation and persistence
• Reeb spaces of piecewise linear mappings
• Self-adjusting binary search trees
• Self-adjusting top trees
• THE AUGMENTED MULTIRESOLUTION REEB GRAPH APPROACH FOR CONTENT-BASED RETRIEVAL OF 3D SHAPES
• Time-varying Reeb graphs for continuous space-time data

Cited in

(7)

• Efficient Output-Sensitive Construction of Reeb Graphs
• Maintaining Reeb graphs of triangulated 2-manifolds
• A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
• Revisiting graph persistence for updates and efficiency
• A refined definition for groups of moving entities and its computation
• Labeled interleaving distance for Reeb graphs
• A deterministic \(O(m \log m)\) time algorithm for the Reeb graph

This page was built for publication: A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph

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