Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier. (English) Zbl 1410.68277
Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 730-739 (2016).
MSC:
68R10 | Graph theory (including graph drawing) in computer science |
68P05 | Data structures |
68Q25 | Analysis of algorithms and problem complexity |
68W27 | Online algorithms; streaming algorithms |