Space complexity of minimum cut problems in single-pass streams
From MaRDI portal
Cites work
- A new approach to the minimum cut problem
- A simple augmentation method for matchings with applications to streaming algorithms
- A simple semi-streaming algorithm for global minimum cuts
- Approximate Maximum Matching in Random Streams
- Approximate sparse recovery: optimizing time and measurements
- Approximating matching size from random streams
- Beating two-thirds for random-order streaming matching
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Communication Complexity
- Computing exact minimum cuts without knowing the graph
- Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
- Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
- Efficient Computations of a Security Index for False Data Attacks in Power Networks
- Estimating graph parameters from random order streams
- Fast and Space Efficient Spectral Sparsification in Dynamic Streams
- Fast approximation algorithms for cut-based problems in undirected graphs
- Graph sparsification by effective resistances
- Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- scientific article; zbMATH DE number 7788450 (Why is no real title available?)
- Intractability of min- and max-cut in streaming graphs
- Maximum matching in semi-streaming with few passes
- Minimum cuts in near-linear time
- Near optimal linear algebra in the online and sliding window models
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On sketching quadratic forms
- On the Edge-Expansion of Graphs
- Online row sampling
- Optimal lower bounds for sketching graph cuts
- Optimal short cycle decomposition in almost linear time
- Random sampling in residual graphs
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Robust lower bounds for communication and stream computation
- Selection and sorting with limited storage
- Single pass spectral sparsification in dynamic streams
- Spectral sparsification of graphs
- Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
- Tight bounds for graph problems in insertion streams
- Twice-Ramanujan sparsifiers
- Vertex Ordering Problems in Directed Graph Streams
- Weighted Matchings via Unweighted Augmentations
- Weighted min-cut: sequential, cut-query, and streaming algorithms
This page was built for publication: Space complexity of minimum cut problems in single-pass streams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296681)
