On graph problems in a semi-streaming model
From MaRDI portal
Publication:2581265
DOI10.1016/j.tcs.2005.09.013zbMath1081.68069OpenAlexW2165753192MaRDI QIDQ2581265
Jian Zhang, Joan Feigenbaum, Sampath Kannan, Siddharth Suri, Andrew McGregor
Publication date: 9 January 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1249&context=cis_papers
Related Items
Optimal In-place Algorithms for Basic Graph Problems ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Finding Articulation Points of Large Graphs in Linear Time ⋮ Streaming deletion problems parameterized by vertex cover ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ On Randomized Algorithms for Matching in the Online Preemptive Model ⋮ Maximum Matching in Turnstile Streams ⋮ A linear time deterministic algorithm to find a small subset that approximates the centroid ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Superlinear lower bounds for multipass graph processing ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Interval selection in the streaming model ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Streaming graph computations with a helpful advisor ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ A one pass streaming algorithm for finding Euler tours ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Distributed coloring of hypergraphs ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Drawing trees in a streaming model ⋮ Improved bounds for randomized preemptive online matching ⋮ Data mining of social networks represented as graphs ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Buyback Problem - Approximate Matroid Intersection with Cancellation Costs ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Structural results on matching estimation with applications to streaming ⋮ Best-order streaming model ⋮ Dynamic Approximate Vertex Cover and Maximum Matching ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Correlation clustering in data streams ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ Depth First Search in the Semi-streaming Model ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Maximum matching on trees in the online preemptive and the incremental graph models ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Linear-time parameterized algorithms with limited local resources
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel approximation algorithms for maximum weighted matching in general graphs
- The space complexity of approximating the frequency moments
- A functional approach to external graph algorithms
- On finding common neighborhoods in massive graphs.
- Fast, small-space algorithms for approximate histogram maintenance
- The Probabilistic Communication Complexity of Set Intersection
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Generating sparse spanners for weighted graphs
- Data-streams and histograms
