Streaming graph computations with a helpful advisor
From MaRDI portal
Publication:1939657
DOI10.1007/s00453-011-9598-yzbMath1259.68038arXiv1004.2899OpenAlexW2176939845MaRDI QIDQ1939657
Justin Thaler, Graham Cormode, Michael Mitzenmacher
Publication date: 5 March 2013
Published in: Algorithmica, Algorithms – ESA 2010 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1004.2899
Numerical mathematical programming methods (65K05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Computer aspects of numerical algorithms (65Y99)
Related Items (10)
A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Best-order streaming model ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Arthur-Merlin streaming complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Checking the correctness of memories
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- A simpler minimum spanning tree verification algorithm
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- On graph problems in a semi-streaming model
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Highly Robust Error Correction byConvex Programming
- Best-Order Streaming Model
- Annotations in Data Streams
- Numerical linear algebra in the streaming model
- Computational Complexity
- Stable signal recovery from incomplete and inaccurate measurements
- Convex separable optimization is not much harder than linear optimization
- Trading off space for passes in graph streaming problems
This page was built for publication: Streaming graph computations with a helpful advisor
