Graph spanners in the streaming model: An experimental study
DOI10.1007/S00453-008-9216-9zbMATH Open1189.68174OpenAlexW2023706097WikidataQ61609524 ScholiaQ61609524MaRDI QIDQ834593FDOQ834593
Authors: Giorgio Ausiello, Camil Demetrescu, Andrea Ribichini, Paolo G. Franciosa, Giuseppe F. Italiano 
Publication date: 27 August 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9216-9
Recommendations
- Graph Sparsification in the Semi-streaming Model
- Computing graph spanners in small memory: fault-tolerance and streaming
- Computing graph spanners in small memory: fault-tolerance and streaming
- A Survey of Graph Algorithms Under Extended Streaming Models of Computation
- On graph problems in a semi-streaming model
- Automata, Languages and Programming
- Spectral sparsification in dynamic graph streams
- scientific article
- Dynamic graph stream algorithms in \(o(n)\) space
- Dynamic graph stream algorithms in \(o(n)\) space
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Nonnumerical algorithms (68W05)
Cites Work
- There are planar graphs almost as good as the complete graph
- Complexity of network synchronization
- An Optimal Synchronizer for the Hypercube
- On sparse spanners of weighted graphs
- Graph spanners
- Grid spanners
- Additive graph spanners
- Automata, Languages and Programming
- Delaunay graphs are almost as good as complete graphs
- Small Stretch Spanners on Dynamic Graphs
- Dynamic Algorithms for Graph Spanners
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- Title not available (Why is that?)
- Graph distances in the streaming model: the value of space
- NP-completeness of minimum spanner problems
- Title not available (Why is that?)
- New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
Cited In (6)
- Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
- Streamed Graph Drawing and the File Maintenance Problem
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- On resilient graph spanners
- Computing graph spanners in small memory: fault-tolerance and streaming
- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
Uses Software
This page was built for publication: Graph spanners in the streaming model: An experimental study
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834593)
