scientific article; zbMATH DE number 7561538

DOI10.4230/LIPIcs.ICALP.2019.45MaRDI QIDQ5091196

Jacques Dark, Christian Konrad, Graham Cormode

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundsstreaming algorithmsindependent set size

Mathematics Subject Classification ID

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

Related Items (8)

Streaming deletion problems parameterized by vertex cover ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams

Cites Work

• Unnamed Item
• Unnamed Item
• On randomized one-round communication complexity
• Approximating the Caro-Wei bound for independent sets in graph streams
• Interval selection in the streaming model
• Computing large independent sets in a single round
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Streaming and Communication Complexity of Clique Approximation
• Maximum Matching in Turnstile Streams
• Streaming Algorithms for Independent Sets
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• Space-Constrained Interval Selection
• Reducibility among Combinatorial Problems
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Nearly complete graphs decomposable into large induced matchings and their applications
• The chromatic number of random graphs

This page was built for publication: