scientific article; zbMATH DE number 7053292

zbMath1422.68176MaRDI QIDQ5743413

Kook Jin Ahn, Sudipto Guha, Andrew McGregor

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095156

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (31)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Sketching and Embedding are Equivalent for Norms ⋮ Separating adaptive streaming from oblivious streaming using the bounded storage model ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Summary Data Structures for Massive Data ⋮ When distributed computation is communication expensive ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ Unnamed Item ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Brief Announcement: MapReduce Algorithms for Massive Trees ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Correlation clustering in data streams ⋮ Public vs. private randomness in simultaneous multi-party communication complexity ⋮ The role of randomness in the broadcast congested clique model ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Optimality of linear sketching under modular updates ⋮ A General Framework for Graph Sparsification ⋮ Better streaming algorithms for the maximum coverage problem ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Connectivity and connected components in the number-in-hand computation model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting distinct items over update streams
• Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
• Weighted matching in the semi-streaming model
• On graph problems in a semi-streaming model
• Random sampling in cut, flow, and network design problems
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Dynamic Connectivity: Connecting to Networks and Geometry
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Near-optimal fully-dynamic graph connectivity
• Extensions of Lipschitz mappings into a Hilbert space
• Fast, small-space algorithms for approximate histogram maintenance
• Algorithms for dynamic geometric problems over data streams
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Graph Sparsification in the Semi-streaming Model
• Graph Distances in the Data-Stream Model
• Sparsification—a technique for speeding up dynamic graph algorithms
• Optimal Two-Stage Algorithms for Group Testing Problems
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Sampling in dynamic data streams and applications
• Continuous sampling from distributed streams
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On the Power of Adaptivity in Sparse Recovery
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Algorithms - ESA 2003
• Compressed sensing

This page was built for publication: