Distributed algorithms for ultrasparse spanners and linear size skeletons

DOI10.1145/1400751.1400786zbMATH Open1301.68259OpenAlexW2032654248MaRDI QIDQ5892001FDOQ5892001

Seth Pettie

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1400751.1400786

Recommendations

• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Fast deterministic distributed algorithms for sparse spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Distributed spanner approximation
• Distributed Spanner Approximation
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• scientific article; zbMATH DE number 2079403
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Improved deterministic distributed construction of spanners

zbMATH Keywords

spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (5)

• Graph spanners: a tutorial review
• Sublinear fully distributed partition with applications
• Distributed constructions of dual-failure fault-tolerant distance preservers
• Distributed Spanner Approximation
• Title not available (Why is that?)

This page was built for publication: Distributed algorithms for ultrasparse spanners and linear size skeletons

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