Independent sets in vertex-arrival streams

DOI10.4230/LIPICS.ICALP.2019.45MaRDI QIDQ5091196zbMATH OpenFDO

Authors Graham Cormode, Jacques Dark, Christian Konrad

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1807.08331

zbMATH Keywords

lower boundsstreaming algorithmsindependent set size

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Streaming Algorithms for Independent Sets
• Streaming algorithms for independent sets in sparse hypergraphs
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Approximating the Caro-Wei bound for independent sets in graph streams
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Approximating the Caro-Wei bound for independent sets in graph streams
• Computing large independent sets in a single round
• 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 \((\Delta + 1)\) vertex coloring
• The chromatic number of random graphs

Cited in

(13)

• On streaming algorithms for geometric independent set and clique
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Streaming Algorithms for Independent Sets
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Fixed parameter tractability of graph deletion problems over data streams
• Streaming deletion problems parameterized by vertex cover
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• Streaming algorithms for independent sets in sparse hypergraphs
• Approximating the Caro-Wei bound for independent sets in graph streams
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• On regularity lemma and barriers in streaming and dynamic matching
• Streaming deletion problems Parameterized by vertex cover

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)