Graph Sparsification in the Semi-streaming Model

DOI10.1007/978-3-642-02930-1_27MaRDI QIDQ3638103zbMATH OpenOpenAlexFDO

Authors Kook Jin Ahn, Sudipto Guha

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Spectral sparsification in the semi-streaming setting
• Spectral sparsification in the semi-streaming setting
• Automata, Languages and Programming
• On graph problems in a semi-streaming model
• A framework for analyzing resparsification algorithms

Cited in

(30)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Intractability of min- and max-cut in streaming graphs
• Space lower bounds for graph stream problems
• Optimal per-edge processing times in the semi-streaming model
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Single pass spectral sparsification in dynamic streams
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Spectral sparsification in the semi-streaming setting
• Streaming algorithms for independent sets in sparse hypergraphs
• Sublinear estimation of weighted matchings in dynamic data streams
• Sparse Cut Projections in Graph Streams
• Graph Distances in the Data-Stream Model
• Spectral sparsification in the semi-streaming setting
• A framework for analyzing resparsification algorithms
• Sublinear algorithms for MAXCUT and correlation clustering
• Sparsification of Binary CSPs
• Polynomial pass lower bounds for graph streaming algorithms
• Sparsification of binary CSPs
• A general framework for graph sparsification
• Sparsification of two-variable valued constraint satisfaction problems
• Tight bounds for graph problems in insertion streams
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
• On the streaming complexity of expander decomposition
• A (3+)-approximate correlation clustering algorithm in dynamic streams
• Additive sparsification of CSPs
• Sparsification of directed graphs via cut balance
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Streaming algorithms for network design
• Graph spanners in the streaming model: An experimental study

This page was built for publication: Graph Sparsification in the Semi-streaming Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638103)