×

A distributed enumeration algorithm and applications to all pairs shortest paths, diameter…. (English) Zbl 1336.68280

Summary: 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)\).

MSC:

68W15 Distributed algorithms
05C30 Enumeration in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Almeida, P. S.; Baquero, C.; Cunha, A., Fast distributed computation of distances in networks (2011)
[2] Alon, N.; Galil, Z.; Margalit, O., On the exponent of the all pairs shortest path problem, (32nd Annual Symposium on Foundations of Computer Science. 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991 (1991)), 569-575
[3] Alon, N.; Galil, Z.; Margalit, O.; Naor, M., Witnesses for boolean matrix multiplication and for shortest paths, (33rd Annual Symposium on Foundations of Computer Science. 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October (1992)), 417-426 · Zbl 0977.68562
[4] Bodlaender, H. L.; Moran, S.; Warmuth, M. K., The distributed bit complexity of the ring: from the anonymous case to the non-anonymous case, Inf. Comput., 114, 2, 34-50 (1994) · Zbl 0801.68076
[5] Bar-Noy, A.; Naor, J.; Naor, M., One-bit algorithms, Distrib. Comput., 4, 3-8 (1990)
[6] Chaudhuri, P., An optimal distributed algorithm for finding articulation points in a network, Comput. Commun., 21, 18, 1707-1715 (1998)
[7] Chen, C., A distributed algorithm for shortest paths, IEEE Trans. Comput., 100, 9, 898-899 (1982)
[8] Chartrand, G.; Kapoor, S. F., The cube of every connected graph is 1-hamiltonian, J. Res. Natl. Bur. Stand. B, 73B, 47-48 (1969) · Zbl 0174.26802
[9] Cormen, Th. H.; Leiserson, Ch. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press
[10] Dor, D.; Halperin, S.; Zwick, U., All-pairs almost shortest paths, SIAM J. Comput., 29, 5, 1740-1759 (2000) · Zbl 0948.05047
[11] Dinitz, Y.; Moran, S.; Rajsbaum, S., Bit complexity of breaking and achieving symmetry in chains and rings, J. ACM, 55, 1 (2008) · Zbl 1326.68035
[12] Elkin, M., Computing almost shortest paths, ACM Trans. Algorithms, 1, 2, 283-323 (2005) · Zbl 1321.05258
[13] Frischknecht, S.; Holzer, S.; Wattenhofer, R., Networks cannot compute their diameter in sublinear time, (SODA (2012)), 1150-1162 · Zbl 1421.68127
[15] Ghaffari, M.; Kuhn, F., Distributed minimum cut approximation, (Distributed Computing - 27th International Symposium Proceedings. Distributed Computing - 27th International Symposium Proceedings, DISC 2013, Jerusalem, Israel, October 14-18 (2013)), 1-15 · Zbl 1435.68379
[16] Hohberg, W., How to find biconnected components in distributed networks, J. Parallel Distrib. Comput., 9, 4, 374-386 (1990)
[17] Harary, F.; Schwenk, A., Trees with hamiltonian square, Mathematika, 18, 138-140 (1971) · Zbl 0221.05052
[18] Holzer, S.; Wattenhofer, R., Optimal distributed all pairs shortest paths and applications, (PODC (2012)), 355-364 · Zbl 1301.68256
[19] Kushilevitz, E.; Nisan, N., Communication Complexity (1999), Cambridge University Press
[20] Kothapalli, K.; Onus, M.; Scheideler, C.; Schindelhauer, C., Distributed coloring in \(O(\sqrt{\log n})\) bit rounds, (Proceedings of the 20th International Parallel and Distributed Processing Symposium. Proceedings of the 20th International Parallel and Distributed Processing Symposium, IPDPS 2006, Greece, Rhodes Island, April (2006), IEEE), 25-29
[21] Lenzen, Ch.; Patt-Shamir, B., Fast routing table construction using small messages: extended abstract, (STOC (2013)), 381-390 · Zbl 1293.68058
[22] Nanongkai, D., Distributed approximation algorithms for weighted shortest paths, (STOC (2014)) · Zbl 1315.05136
[23] Peleg, D., Distributed Computing - A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications (2000) · Zbl 0959.68042
[24] Peleg, D.; Roditty, L.; Tal, E., Distributed algorithms for network diameter and girth, (ICALP (2) (2012)), 660-672 · Zbl 1343.68283
[25] Pritchard, D.; Thurimella, R., Fast computation of small cuts via cycle space sampling, ACM Trans. Algorithms, 7, 4, 46 (2011) · Zbl 1295.68205
[26] Rosen, Kenneth H., Handbook of Discrete and Combinatorial Mathematics (2000), CRC Press · Zbl 1044.00002
[27] Radoszewski, J.; Rytter, W., Hamiltonian paths in the square of a tree, (ISAAC (2011)), 90-99 · Zbl 1349.05200
[28] Roditty, L.; Tov, R., Approximating the girth, (SODA (2011)), 1446-1454 · Zbl 1376.68173
[29] Roditty, L.; Williams, V. V., Minimum weight cycles and triangles: equivalences and algorithms, (FOCS (2011)), 180-189 · Zbl 1292.05155
[30] Roditty, L.; Williams, V. V., Subquadratic time approximation algorithms for the girth, (SODA (2012)), 833-845 · Zbl 1423.05183
[31] Sekanina, M., On an algorithm for ordering of graphs, Can. Math. Bull., 14, 2, 221-224 (1971) · Zbl 0215.33903
[32] Sarma, Das; Holzer, S.; Kor, L.; Korman, A.; Nanongkai, D.; Pandurangan, G.; Peleg, D.; Wattenhofer, R., Distributed verification and hardness of distributed approximation, SIAM J. Comput., 41, 5, 1235-1265 (2012) · Zbl 1259.68227
[33] Schneider, J.; Wattenhofer, R., Trading bit, message, and time complexity of distributed algorithms, (Distributed Computing - 25th International Symposium, Proceedings. Distributed Computing - 25th International Symposium, Proceedings, DISC 2011, Rome, Italy, September 20-22 (2011)), 51-65 · Zbl 1350.68282
[34] Tel, G., Introduction to Distributed Algorithms (2000), Cambridge University Press · Zbl 0961.68157
[35] Thurimella, R., Sub-linear distributed algorithms for sparse certificates and biconnected components, J. Algorithms, 23, 1, 160-179 (1997) · Zbl 0871.68090
[36] Toueg, S., An all-pairs shortest-paths distributed algorithm (1980), IBM T.J. Watson Research Center: IBM T.J. Watson Research Center Yorktown Heights, NY 10598, USA, Technical Report, RC 8327
[37] Williams, V. V.; Williams, R., Subcubic equivalences between path, matrix and triangle problems, (FOCS (2010)), 645-654
[38] Yao, A. C., Some complexity questions related to distributed computing, (Proceedings of the 11th ACM Symposium on Theory of computing. Proceedings of the 11th ACM Symposium on Theory of computing, STOC (1979), ACM Press), 209-213
[39] Zwick, U., All pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM, 49, 3, 289-317 (2002) · Zbl 1326.05157
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.