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

DOI10.1016/j.ic.2015.12.004zbMath1336.68280arXiv1507.03376OpenAlexW2221641379MaRDI QIDQ259059

Akka Zemmari, John Michael Robson, Yves Métivier

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

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

Related Items (2)

On the Microscopic View of Time and Messages ⋮ Small-\(m\) method for detecting all longest paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Distributed Minimum Cut Approximation
• Optimal distributed all pairs shortest paths and applications
• Trading Bit, Message, and Time Complexity of Distributed Algorithms
• Hamiltonian Paths in the Square of a Tree
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Distributed Algorithms for Network Diameter and Girth
• Fast computation of small cuts via cycle space sampling
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Bit complexity of breaking and achieving symmetry in chains and rings
• Distributed Computing: A Locality-Sensitive Approach
• Introduction to Distributed Algorithms
• Distributed Verification and Hardness of Distributed Approximation
• All-Pairs Almost Shortest Paths
• Distributed approximation algorithms for weighted shortest paths
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Fast routing table construction using small messages
• The cube of every connected graph is 1-hamiltonian
• On an Algorithm for Ordering of Graphs
• Trees with Hamiltonian square
• Computing almost shortest paths

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