Sparse Cut Projections in Graph Streams

DOI10.1007/978-3-642-04128-0_43MaRDI QIDQ3639268zbMATH OpenOpenAlexFDO

Authors Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_43

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph Sparsification in the Semi-streaming Model
• Finding small sparse cuts by random walk
• Finding sparse cuts locally using evolving sets
• Intractability of min- and max-cut in streaming graphs
• Distributed sparse cut approximation

Cited in

(1)

• Sparsest cuts and concurrent flows in product graphs.

This page was built for publication: Sparse Cut Projections in Graph Streams

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