Graph Distances in the Data-Stream Model
From MaRDI portal
Publication:3642861
DOI10.1137/070683155zbMath1181.68153OpenAlexW2148137544MaRDI QIDQ3642861
Andrew McGregor, Jian Zhang, Siddharth Suri, Sampath Kannan, Joan Feigenbaum
Publication date: 6 November 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070683155
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Finding Articulation Points of Large Graphs in Linear Time ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Superlinear lower bounds for multipass graph processing ⋮ Unnamed Item ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ On the behaviour of \(K\)-means clustering of a dissimilarity matrix by means of full multidimensional scaling ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Unnamed Item
This page was built for publication: Graph Distances in the Data-Stream Model
