Graph spanners in the streaming model: An experimental study
type: Item
instance of: scholarly article
title: Graph spanners in the streaming model: An experimental study
zbMATH Open document ID: 1189.68174
author: Giorgio Ausiello
author: Camil Demetrescu
author: Andrea Ribichini
author: Paolo G. Franciosa
author: Giuseppe F. Italiano
published in: Algorithmica
publication date: 2009-08-27T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 5598786
zbMATH Keywords: graph algorithms
zbMATH Keywords: graph spanners
zbMATH Keywords: data streams
zbMATH Keywords: experimental algorithmics
zbMATH Keywords: algorithm engineering
describes a project that uses: spanner
MaRDI profile type: Publication
full work available at URL: s00453-008-9216-9
OpenAlex ID: W2023706097
cites work: On sparse spanners of weighted graphs
cites work: Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
cites work: Small Stretch Spanners on Dynamic Graphs
cites work: Complexity of network synchronization
cites work: Dynamic Algorithms for Graph Spanners
cites work: New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
cites work: Q4449190
cites work: NP-completeness of minimum spanner problems
cites work: There are planar graphs almost as good as the complete graph
cites work: Q3484375
cites work: Delaunay graphs are almost as good as complete graphs
cites work: Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
cites work: Relaxing the uniformity and independence assumptions using the concept of fractal dimension
cites work: Graph distances in the streaming model: the value of space
cites work: Additive graph spanners
cites work: Grid spanners
cites work: Graph spanners
cites work: An Optimal Synchronizer for the Hypercube
cites work: Automata, Languages and Programming
Wikidata QID: Q61609524
DOI: 10.1007/S00453-008-9216-9
Recommended article: Graph Sparsification in the Semi-streaming Model
Recommended article: Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming
Recommended article: COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
Recommended article: A Survey of Graph Algorithms Under Extended Streaming Models of Computation
Recommended article: On graph problems in a semi-streaming model
Recommended article: Automata, Languages and Programming
Recommended article: Spectral Sparsification in Dynamic Graph Streams
Recommended article: Q3139291
Recommended article: Q4598151
Recommended article: Dynamic graph stream algorithms in \(o(n)\) space
description: scientific article; zbMATH DE number 5598786