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

DOI10.1007/978-3-540-73420-8_62MaRDI QIDQ5428852zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Fully dynamic randomized algorithms for graph spanners
• Dynamic Algorithms for Graph Spanners
• Small Stretch Spanners on Dynamic Graphs

Cited in

(8)

• Intractability of min- and max-cut in streaming graphs
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Graph spanners in the streaming model: An experimental study
• Small stretch ( , )-spanners in the streaming model
• Streaming algorithm for graph spanners-single pass and constant processing time per edge

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428852)