Depth First Search in the Semi-streaming Model
From MaRDI portal
Publication:5090492
DOI10.4230/LIPIcs.STACS.2019.42OpenAlexW2963850880MaRDI QIDQ5090492
Shahbaz Khan, Shashank K. Mehta
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1901.03689
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superlinear lower bounds for multipass graph processing
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Probabilistic counting algorithms for data base applications
- Maintaining bridge-connected and biconnected components on-line
- Edge-disjoint spanning trees and depth-first search
- The space complexity of approximating the frequency moments
- On finding common neighborhoods in massive graphs.
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- On graph problems in a semi-streaming model
- Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Finding Articulation Points of Large Graphs in Linear Time
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Worst-case Analysis of Set Union Algorithms
- Finding Dominators in Directed Graphs
- Efficient Planarity Testing
- Efficiency of a Good But Not Linear Set Union Algorithm
- Network Flow and Testing Graph Connectivity
- Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Distributed exact shortest paths in sublinear time
- Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
- Data-streams and histograms
- A Survey of Graph Algorithms Under Extended Streaming Models of Computation
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Depth-First Search and Linear Graph Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Better bounds for matchings in the streaming model
This page was built for publication: Depth First Search in the Semi-streaming Model