Orthogonal range search is ubiquitous nowadays, with natural applications in databases, data mining, and text indexing. Very recently, yet another application was discovered, which is to maintain a DFS forest in a dynamic graph. In this paper, we want to extend the above recent study, by applying orthogonal range search to efficient maintenance of a BFS-like forest, called no-back-edge-traversal (NBET) forest, which refers to a spanning forest obtained from a traversal that does not create any back edge. The study of such a problem is motivated by the fact that NBET forest can be used as a strong certificate of 2-connectivity of an undirected graph, which is more general than a spanning forest obtained from a scan-first search traversal.

Communicated by D T Lee

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

1. M. Lewenstein, Orthogonal range searching for text indexing, in Space-Efficient Data Structures, Streams, and Algorithms (2013), pp. 267–302. Google Scholar
2. T. Gagie, G. Navarro and N. Prezza, Fully functional suffix trees and optimal text searching in BWT-runs bounded space, Journal of the ACM 67(1) (2020) 2:1–2:54. Crossref, Web of Science, Google Scholar
3. S. Baswana, S. R. Chaudhury, K. Choudhary and S. Khan, Dynamic DFS in undirected graphs: Breaking the O(m) barrier, SIAM Journal on Computing 48(4) (2019) 1335–1363. Crossref, Web of Science, Google Scholar
4. K. Nakamura and K. Sadakane, Space-efficient fully dynamic DFS in undirected graphs, Algorithms 12(3) (2019) 52:1–52:24. Crossref, Web of Science, Google Scholar
5. J. Cheriyan, M. Kao and R. Thurimella, Scan-first search and sparse certificates: An improved parallel algorithms for $k$ $k$ -vertex connectivity, SIAM Journal on Computing 22(1) (1993) 157–174. Crossref, Web of Science, Google Scholar
6. H. Nagamochi and T. Ibaraki, A linear-time algorithm for finding a sparse $k$ $k$ -connected spanning subgraph of a $k$ $k$ -connected graph, Algorithmica 7(5–6) (1992) 583–596. Crossref, Web of Science, Google Scholar
7. D. Eppstein, Z. Galil, G. F. Italiano and A. Nissenzweig, Sparsification — a technique for speeding up dynamic graph algorithms, Journal of the ACM 44(5) (1997) 669–696. Crossref, Web of Science, Google Scholar
8. S. Guha, A. McGregor and D. Tench, Vertex and hyperedge connectivity in dynamic graph streams, in Symposium on Principles of Database Systems (2015), pp. 241–247. Crossref, Google Scholar
9. T. Chan, K. Larson and M. Pătraşcu, Orthogonal range searching on the RAM, revisited, in ACM Symposium on Computational Geometry (2011), pp. 1–10. Crossref, Google Scholar
10. Range Searching, https://en.wikipedia.org/wiki/Range_searching, accessed: 2022-12-03. Google Scholar
11. D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences 26(3) (1983) 362–391. Crossref, Web of Science, Google Scholar