Depth First Search in the Semi-streaming Model

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

zbMATH Keywords

algorithmDFSstreamingdepth first searchsemi-streaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 L¹ -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