On graph problems in a semi-streaming model
From MaRDI portal
Publication:2581265
Recommendations
Cites work
- A functional approach to external graph algorithms
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Data streams: algorithms and applications.
- Data-streams and histograms
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast, small-space algorithms for approximate histogram maintenance
- Generating sparse spanners for weighted graphs
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 1151367 (Why is no real title available?)
- scientific article; zbMATH DE number 2079343 (Why is no real title available?)
- scientific article; zbMATH DE number 2119719 (Why is no real title available?)
- scientific article; zbMATH DE number 1424324 (Why is no real title available?)
- On finding common neighborhoods in massive graphs.
- Parallel approximation algorithms for maximum weighted matching in general graphs
- The Probabilistic Communication Complexity of Set Intersection
- The space complexity of approximating the frequency moments
Cited in
(93)- Improved bounds for randomized preemptive online matching
- On extensions of the deterministic online model for bipartite matching and max-sat
- Dynamic graph stream algorithms in \(o(n)\) space
- Structural results on matching estimation with applications to streaming
- On finding common neighborhoods in massive graphs.
- Graph spanners: a tutorial review
- Correlation clustering in data streams
- Almost-smooth histograms and sliding-window graph algorithms
- Linear-time parameterized algorithms with limited local resources
- Streaming deletion problems parameterized by vertex cover
- Labeled graph sketches: keeping up with real-time graph streams
- Frameworks for designing in-place graph algorithms
- Maximum matching on trees in the online preemptive and the incremental graph models
- Optimal per-edge processing times in the semi-streaming model
- A linear time deterministic algorithm to find a small subset that approximates the centroid
- Graph sketching and streaming: new approaches for analyzing massive graphs
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Streamed Graph Drawing and the File Maintenance Problem
- Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
- Single pass spectral sparsification in dynamic streams
- Buyback problem -- approximate matroid intersection with cancellation costs
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Streaming algorithms for independent sets in sparse hypergraphs
- Superlinear lower bounds for multipass graph processing
- Streaming algorithms for submodular function maximization
- Finding articulation points of large graphs in linear time
- Sublinear estimation of weighted matchings in dynamic data streams
- On randomized algorithms for matching in the online preemptive model
- Maximum matching in turnstile streams
- Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems
- Graph Sparsification in the Semi-streaming Model
- Bipartite Graph Matchings in the Semi-streaming Model
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- Drawing trees in a streaming model
- Semi-streaming algorithms for annotated graph streams
- Data mining of social networks represented as graphs
- Dynamic approximate vertex cover and maximum matching
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- 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 in two, three, and a few more passes over graph streams
- A simple augmentation method for matchings with applications to streaming algorithms
- A framework for in-place graph algorithms
- Optimal In-place Algorithms for Basic Graph Problems
- Simulating random walks on graphs in the streaming model
- Depth First Search in the Semi-streaming Model
- Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- A Survey of Graph Algorithms Under Extended Streaming Models of Computation
- Best-order streaming model
- Computing the degeneracy of large graphs
- Automata, Languages and Programming
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Trading off space for passes in graph streaming problems
- Semi-streaming algorithms for submodular matroid intersection
- Semi-streaming algorithms for submodular matroid intersection
- Streaming deletion problems Parameterized by vertex cover
- Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
- Deterministic graph coloring in the streaming model
- Distributed Testing of Graph Isomorphism in the CONGEST Model.
- 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
- On regularity lemma and barriers in streaming and dynamic matching
- (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Parameterized complexity of streaming diameter and connectivity problems
- Improved bounds for matching in random-order streams
- Semi-streaming algorithms for submodular function maximization under \(b\)-matching, matroid, and matchoid constraints
- Constructing large matchings via query access to a maximal matching oracle
- Improved bounds for matching in random-order streams
- Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
- Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
- A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
- Weighted matching in the random-order streaming and robust communication models
- Temporal separators with deadlines
- Parameterized complexity of streaming diameter and connectivity problems
- Maximum weight b-matchings in random-order streams
- Streaming graph algorithms in the massively parallel computation model
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- A (3+)-approximate correlation clustering algorithm in dynamic streams
- Maximum coverage in the data stream model: parameterized and generalized
- Beating two-thirds for random-order streaming matching
- Semi-streaming algorithms for weighted k-disjoint matchings
- Matchings in low-arboricity graphs in the dynamic graph stream model
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Graph spanners in the streaming model: An experimental study
- New results for finding common neighborhoods in massive graphs in the data stream model
This page was built for publication: On graph problems in a semi-streaming model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581265)
