Graph spanners in the streaming model: An experimental study

DOI10.1007/S00453-008-9216-9MaRDI QIDQ834593zbMATHOpenAlexWikidataFDO

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

zbMATH Keywords

graph algorithmsdata streamsgraph spannersalgorithm engineeringexperimental algorithmics

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Nonnumerical algorithms (68W05)

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; zbMATH DE number 434498
• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space

Cites work

• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• Additive graph spanners
• An Optimal Synchronizer for the Hypercube
• Automata, Languages and Programming
• Complexity of network synchronization
• Delaunay graphs are almost as good as complete graphs
• Dynamic Algorithms for Graph Spanners
• Graph distances in the streaming model: the value of space
• Graph spanners
• Grid spanners
• NP-completeness of minimum spanner problems
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• On sparse spanners of weighted graphs
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Small Stretch Spanners on Dynamic Graphs
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• There are planar graphs almost as good as the complete graph

Cited in

(5)

• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Streamed Graph Drawing and the File Maintenance Problem
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• Computing graph spanners in small memory: fault-tolerance and streaming
• Small stretch \((\alpha ,\beta )\)-spanners in the streaming model

Describes a project that uses

Uses Software

• spanner

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)