scientific article; zbMATH DE number 7053292
From MaRDI portal
Publication:5743413
Recommendations
- scientific article; zbMATH DE number 4089609
- Measuring Structural Similarities of Graphs in Linear Time
- On the structure of linear graphs
- On the structure of linear graphs
- scientific article; zbMATH DE number 5575767
- Linear layouts measuring neighbourhoods in graphs
- scientific article; zbMATH DE number 851959
- Recovering the structure of random linear graphs
Cites work
- 1-pass relative-error L_p-sampling with applications
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Algorithms - ESA 2003
- Algorithms for dynamic geometric problems over data streams
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Compressed sensing
- Continuous sampling from distributed streams
- Counting distinct items over update streams
- Data streams: algorithms and applications.
- Dynamic connectivity: connecting to networks and geometry
- Extensions of Lipschitz mappings into a Hilbert space
- Fast, small-space algorithms for approximate histogram maintenance
- Graph Distances in the Data-Stream Model
- Graph Sparsification in the Semi-streaming Model
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
- IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Near-optimal fully-dynamic graph connectivity
- On graph problems in a semi-streaming model
- On the Power of Adaptivity in Sparse Recovery
- Optimal Two-Stage Algorithms for Group Testing Problems
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Random sampling in cut, flow, and network design problems
- Sampling in dynamic data streams and applications
- Sparsification—a technique for speeding up dynamic graph algorithms
- Spectral sparsification in the semi-streaming setting
- Weighted matching in the semi-streaming model
- Worst-case update times for fully-dynamic all-pairs shortest paths
Cited in
(61)- Dynamic graph stream algorithms in \(o(n)\) space
- Graph spanners: a tutorial review
- Correlation clustering in data streams
- The role of randomness in the broadcast congested clique model
- Constant-time dynamic weight approximation for minimum spanning forest
- Connectivity and connected components in the number-in-hand computation model
- Equivalence classes and conditional hardness in massively parallel computations
- Separating adaptive streaming from oblivious streaming using the bounded storage model
- Communication complexity of approximate maximum matching in the message-passing model
- Sublinear update time randomized algorithms for dynamic graph regression
- Public vs. private randomness in simultaneous multi-party communication complexity
- Better streaming algorithms for the maximum coverage problem
- Graph sketching and streaming: new approaches for analyzing massive graphs
- Support measures for graph data
- Single-pass streaming algorithms to partition graphs into few forests
- On sketching quadratic forms
- Spanners and sparsifiers in dynamic streams
- Single pass spectral sparsification in dynamic streams
- Measuring Structural Similarities of Graphs in Linear Time
- Connectivity oracles for graphs subject to vertex failures
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- Sketching and embedding are equivalent for norms
- Dynamic graph stream algorithms in \(o(n)\) space
- Brief announcement: MapReduce algorithms for massive trees
- Online facility location with deletions
- A Framework for Adversarially Robust Streaming Algorithms
- Simulating random walks on graphs in the streaming model
- Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
- Optimality of linear sketching under modular updates
- Optimal lower bounds for matching and vertex cover in dynamic graph streams
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- The impact of locality in the broadcast congested clique model
- A general framework for graph sparsification
- Optimal lower bounds for sketching graph cuts
- Summary data structures for massive data
- scientific article; zbMATH DE number 7758324 (Why is no real title available?)
- Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Adversarially robust streaming algorithms via differential privacy
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Near-optimal distributed computation of small vertex cuts
- Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
- Streaming edge coloring with asymptotically optimal colors
- On the cut-query complexity of approximating max-cut
- On the streaming complexity of expander decomposition
- New lower bounds in Merlin-Arthur communication and graph streaming verification
- Time- and communication-efficient overlay network construction via gossip
- Massively parallel computation in a heterogeneous regime
- Rounds vs. communication tradeoffs for maximal independent sets
- A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
- Non-adaptive edge counting and sampling via bipartite independent set queries
- Streaming graph algorithms in the massively parallel computation model
- Deterministic fault-tolerant connectivity labeling scheme
- A (3+)-approximate correlation clustering algorithm in dynamic streams
- Learning spanning forests optimally in weighted undirected graphs with CUT queries
- Sparsification of directed graphs via cut balance
- Fault-tolerant labeling and compact routing schemes
- Streaming maximal matching with bounded deletions
- Near-optimal hypergraph sparsification in insertion-only and bounded-deletion streams
- Overlay network construction: improved overall and node-wise message complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743413)
