Distributed algorithms for network diameter and girth

DOI10.1007/978-3-642-31585-5_58MaRDI QIDQ3167054zbMATH OpenOpenAlexFDO

Authors Liam Roditty, Elad Tal, David Peleg

Publication date 1 November 2012

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

Full work available at URL https://doi.org/10.1007/978-3-642-31585-5_58

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• Networks cannot compute their diameter in sublinear time
• Optimal distributed all pairs shortest paths and applications
• A note on hardness of diameter approximation
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Fast approximation algorithms for the diameter and radius of sparse graphs

Cited in

(27)

• Distributed distance measurement for large-scale networks.
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• A note on hardness of diameter approximation
• Fast approximate shortest paths in the congested clique
• Distributed distance computation and routing with small messages
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Distributed finite-time calculation of node eccentricities, graph radius and graph diameter
• The cost of unknown diameter in dynamic networks
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Performance and robustness of discrete and finite time average consensus algorithms
• Quantum advantage for the LOCAL model in distributed computing
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Distributed graph algorithms and their complexity: an introduction
• Efficient distributed source detection with limited bandwidth
• Sublinear-time quantum computation of the diameter in CONGEST networks
• Efficient and decentralized polling protocol for general social networks
• Distributed Strong Diameter Network Decomposition
• Networks cannot compute their diameter in sublinear time
• Distributed MST for constant diameter graphs
• Approximate proof-labeling schemes
• Improved hardness of approximation of diameter in the CONGEST model
• Fast distributed algorithms for girth, cycles and small subgraphs
• Distributed distance approximation
• Quantum distributed complexity of set disjointness on a line
• Computing minimum weight cycle in the CONGEST model
• Distance computations in the hybrid network model via oracle simulations

This page was built for publication: Distributed algorithms for network diameter and girth

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