Independent sets in vertex-arrival streams
From MaRDI portal
Publication:5091196
Recommendations
Cites work
- Approximating the Caro-Wei bound for independent sets in graph streams
- Computing large independent sets in a single round
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Maximum matching in turnstile streams
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- Nearly complete graphs decomposable into large induced matchings and their applications
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- On randomized one-round communication complexity
- Reducibility among combinatorial problems
- Space-constrained interval selection
- Streaming Algorithms for Independent Sets
- Streaming and communication complexity of clique approximation
- Sublinear algorithms for ( + 1) vertex coloring
- The chromatic number of random graphs
Cited in
(22)- Approximating the Caro-Wei bound for independent sets in graph streams
- Fixed parameter tractability of graph deletion problems over data streams
- Streaming deletion problems parameterized by vertex cover
- Streaming algorithms for independent sets in sparse hypergraphs
- Streaming Algorithms for Independent Sets
- Optimal lower bounds for matching and vertex cover in dynamic graph streams
- scientific article; zbMATH DE number 7651158 (Why is no real title available?)
- Streaming deletion problems Parameterized by vertex cover
- scientific article; zbMATH DE number 7758324 (Why is no real title available?)
- On streaming algorithms for geometric independent set and clique
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- On regularity lemma and barriers in streaming and dynamic matching
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Rounds vs. communication tradeoffs for maximal independent sets
- Interval selection in data streams: weighted intervals and the insertion-deletion setting
- Submodular maximization subject to matroid intersection on the fly
- A (3+)-approximate correlation clustering algorithm in dynamic streams
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Even the easiest(?) Graph coloring problem is not easy in streaming!
- Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
- Constructing long paths in graph streams
- Almost optimal superconstant-pass streaming lower bounds for reachability
This page was built for publication: Independent sets in vertex-arrival streams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091196)
