A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

DOI10.1016/J.IC.2015.12.004MaRDI QIDQ259059zbMATHOpenAlexFDO

Authors Yves Métivier, John Michael Robson, A. Zemmari

Publication date 10 March 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03376

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Distributed algorithms (68W15)

Abstract: We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size $O(1)$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most $3$. We prove that its time complexity is $O(n)$ where $n$ is the number of vertices of the graph. Furthermore, the size of each message is $O(1)$ thus its bit complexity is also $O(n).$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most $2$. We deduce from this enumeration algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to $O(n)$. This improves the best known distributed algorithms (under the same hypotheses) for computing all pairs shortest paths or the diameter presented in cite{PRT12,HW12} having a time complexity equal to $O(n)$ and which use messages of size $O(logn)$ bits.

Recommendations

• Optimal distributed all pairs shortest paths and applications
• scientific article; zbMATH DE number 1304097
• An ‘All Pairs Shortest Paths’ Distributed Algorithm Using 2n2Messages
• A distributed algorithm for constructing a minimum diameter spanning tree

Cites work

• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 1277120 (Why is no real title available?)
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-Pairs Almost Shortest Paths
• Approximating the girth
• Bit complexity of breaking and achieving symmetry in chains and rings
• Computing almost shortest paths
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for network diameter and girth
• Distributed approximation algorithms for weighted shortest paths
• Distributed minimum cut approximation
• Distributed verification and hardness of distributed approximation
• Fast computation of small cuts via cycle space sampling
• Fast routing table construction using small messages (extended abstract)
• Hamiltonian paths in the square of a tree
• Introduction to Distributed Algorithms
• Introduction to algorithms.
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Networks cannot compute their diameter in sublinear time
• On an Algorithm for Ordering of Graphs
• Optimal distributed all pairs shortest paths and applications
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• The cube of every connected graph is 1-hamiltonian
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Trading bit, message, and time complexity of distributed algorithms
• Trees with Hamiltonian square

Cited in

(4)

• Succinct enumeration of distant vertex pairs
• On the microscopic view of time and messages
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• Small-\(m\) method for detecting all longest paths

This page was built for publication: A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

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