Graph Sparsification in the Semi-streaming Model
From MaRDI portal
Publication:3638103
DOI10.1007/978-3-642-02930-1_27zbMath1248.68567OpenAlexW1618327071MaRDI QIDQ3638103
Publication date: 14 July 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02930-1_27
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items (14)
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Spectral sparsification in the semi-streaming setting ⋮ Sparsification of Binary CSPs ⋮ New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ New bounds for the CLIQUE-GAP problem using graph decomposition theory ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Sparsification of Binary CSPs ⋮ A General Framework for Graph Sparsification ⋮ Unnamed Item ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems
This page was built for publication: Graph Sparsification in the Semi-streaming Model
