Graph spanners in the streaming model: An experimental study

DOI10.1007/s00453-008-9216-9zbMath1189.68174OpenAlexW2023706097WikidataQ61609524 ScholiaQ61609524MaRDI QIDQ834593

Camil Demetrescu, Giorgio Ausiello, Andrea Ribichini, Giuseppe F. Italiano, Paolo Giulio Franciosa

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 spannersgraph algorithmsdata streamsalgorithm engineeringexperimental algorithmics

Mathematics Subject Classification ID

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

Related Items

On resilient graph spanners ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING

Uses Software

• spanner

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• There are planar graphs almost as good as the complete graph
• Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
• Complexity of network synchronization
• Graph spanners
• An Optimal Synchronizer for the Hypercube
• Grid spanners
• Additive graph spanners
• Small Stretch Spanners on Dynamic Graphs
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Dynamic Algorithms for Graph Spanners
• Automata, Languages and Programming