Dynamic graph stream algorithms in \(o(n)\) space

DOI10.1007/s00453-018-0520-8zbMath1422.68322WikidataQ64109576 ScholiaQ64109576MaRDI QIDQ1741857

Zengfeng Huang, Pan Peng

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0520-8

zbMATH Keywords

minimum spanning tree; property testing; dynamic graph streams; graph sketching

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing Eulerianity and connectivity in directed sparse graphs
• Correlation clustering in data streams
• An estimator for matching size in low arboricity graphs with two applications
• On graph problems in a semi-streaming model
• Streaming Kernelization
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Spanners and sparsifiers in dynamic streams
• Densest Subgraph in Dynamic Graph Streams
• Single Pass Spectral Sparsification in Dynamic Streams
• Sketching Cuts in Graphs and Hypergraphs
• Property testing and its connection to learning and approximation
• Sublinear Time Algorithms
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Maximum Matching in Turnstile Streams
• Property Testing on k-Vertex-Connectivity of Graphs
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Graph Distances in the Data-Stream Model
• Testing the diameter of graphs
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• Introduction to Testing Graph Properties
• lgorithmic and Analysis Techniques in Property Testing
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Streaming Lower Bounds for Approximating MAX-CUT
• Efficient Sketches for the Set Query Problem
• Sampling in dynamic data streams and applications
• Approximating matching size from random streams
• Planar Graphs: Random Walks and Bipartiteness Testing
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Property testing in bounded degree graphs