Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

DOI10.1137/1.9781611974331.CH52zbMath1410.68277arXiv1502.02481OpenAlexW1721652159MaRDI QIDQ4575631

Shreejit Ray Chaudhury, Surender Baswana, Shahbaz Khan, Keerti Choudhary

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.02481

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Online algorithms; streaming algorithms (68W27)

Related Items (14)

Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Unnamed Item ⋮ Sublinear-time reductions for big data computing ⋮ Unnamed Item ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Depth First Search in the Semi-streaming Model ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Output sensitive fault tolerant maximum matching

This page was built for publication: Dynamic DFS in Undirected Graphs: breaking the O(m) barrier