Dynamic graph stream algorithms in \(o(n)\) space
type: Item
instance of: scholarly article
title: Dynamic graph stream algorithms in \(o(n)\) space
zbMATH Open document ID: 1422.68322
author: Zengfeng Huang
author: Pan Peng
published in: Algorithmica
publication date: 2019-05-07T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7051772
zbMATH Keywords: dynamic graph streams
zbMATH Keywords: graph sketching
zbMATH Keywords: property testing
zbMATH Keywords: minimum spanning tree
Wikidata QID: Q64109576
MaRDI profile type: Publication
full work available at URL: s00453-018-0520-8
OpenAlex ID: W2964299325
cites work: Correlation clustering in data streams
cites work: Q5743413
cites work: Q4228450
cites work: Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
cites work: Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
cites work: Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
cites work: Approximating the Minimum Spanning Tree Weight in Sublinear Time
cites work: Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
cites work: Parameterized Streaming: Maximal Matching and Vertex Cover
cites work: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
cites work: Planar Graphs: Random Walks and Bipartiteness Testing
cites work: Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
cites work: Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
cites work: Streaming Kernelization
cites work: On graph problems in a semi-streaming model
cites work: Graph Distances in the Data-Stream Model
cites work: Sampling in dynamic data streams and applications
cites work: Introduction to Testing Graph Properties
cites work: Property testing and its connection to learning and approximation
cites work: Property testing in bounded degree graphs
cites work: Q4945538
cites work: An estimator for matching size in low arboricity graphs with two applications
cites work: Approximating matching size from random streams
cites work: Streaming Lower Bounds for Approximating MAX-CUT
cites work: Single Pass Spectral Sparsification in Dynamic Streams
cites work: Spanners and sparsifiers in dynamic streams
cites work: Sketching Cuts in Graphs and Hypergraphs
cites work: Maximum Matching in Turnstile Streams
cites work: Densest Subgraph in Dynamic Graph Streams
cites work: Q3425115
cites work: Testing Eulerianity and connectivity in directed sparse graphs
cites work: Testing the diameter of graphs
cites work: Q4608052
cites work: Efficient Sketches for the Set Query Problem
cites work: lgorithmic and Analysis Techniques in Property Testing
cites work: Sublinear Time Algorithms
cites work: Tight Bounds for Graph Problems in Insertion Streams
cites work: Q5365017
cites work: Property Testing on k-Vertex-Connectivity of Graphs
DBLP publication ID: journals/algorithmica/HuangP19
DOI: 10.1007/S00453-018-0520-8
Recommended article: Q4598151
Recommended article: Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Recommended article: Space lower bounds for graph stream problems
Recommended article: Dynamic Algorithms for Graph Spanners
Recommended article: Data Stream Algorithms via Expander Graphs
Recommended article: The State of the Art in Dynamic Graph Algorithms
Recommended article: A Survey of Graph Algorithms Under Extended Streaming Models of Computation
Recommended article: Spectral Sparsification in Dynamic Graph Streams
Recommended article: Q2721962
Recommended article: Algorithmic aspects in speech recognition
description: scientific article; zbMATH DE number 7051772