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

DOI10.1007/s00453-018-0520-8zbMath1422.68322OpenAlexW2964299325WikidataQ64109576 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 treeproperty testingdynamic graph streamsgraph sketching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest

Cites Work

• 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
• Tight Bounds for Graph Problems in Insertion Streams
• 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

This page was built for publication: Dynamic graph stream algorithms in \(o(n)\) space