Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners

DOI10.1007/978-3-540-73420-8_62zbMath1171.68838OpenAlexW1863701533MaRDI QIDQ5428852

Michael Elkin

Publication date: 28 November 2007

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_62

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01)

Related Items (6)

Graph spanners in the streaming model: An experimental study ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Streaming algorithm for graph spanners-single pass and constant processing time per edge ⋮ Distributed construction of purely additive spanners ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons

This page was built for publication: Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners