Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries

DOI10.1142/s0218195922410047OpenAlexW4319970870MaRDI QIDQ6173217

Kunihiko Sadakane, Meng-Tsung Tsai, Wing-Kai Hon, Chung-Shou Liao, Unnamed Author

Publication date: 21 July 2023

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195922410047

zbMATH Keywords

indexingrange searchingdynamic graphsNBET forest

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A data structure for dynamic trees
• Space-efficient fully dynamic DFS in undirected graphs
• Orthogonal Range Searching for Text Indexing
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Sparsification—a technique for speeding up dynamic graph algorithms
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
• Orthogonal range searching on the RAM, revisited

This page was built for publication: Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries