Independent sets in vertex-arrival streams

DOI10.4230/LIPICS.ICALP.2019.45MaRDI QIDQ5091196FDOQ5091196

Authors: Graham Cormode, Jacques Dark, Christian Konrad 

Publication date: 21 July 2022

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

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

zbMATH Keywords

lower boundsstreaming algorithmsindependent set size

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The chromatic number of random graphs
• Streaming and communication complexity of clique approximation
• Streaming Algorithms for Independent Sets
• On randomized one-round communication complexity
• Title not available (Why is that?)
• Nearly complete graphs decomposable into large induced matchings and their applications
• Approximating the Caro-Wei bound for independent sets in graph streams
• Space-constrained interval selection
• Computing large independent sets in a single round
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Maximum matching in turnstile streams
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Sublinear algorithms for \((\Delta + 1)\) vertex coloring

Cited In (13)

• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• On regularity lemma and barriers in streaming and dynamic matching
• Streaming deletion problems Parameterized by vertex cover
• On streaming algorithms for geometric independent set and clique

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)