logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 11 : 212101(2021) https://doi.org/10.1007/s11432-020-2931-x

A nearly optimal distributed algorithm for computing the weighted girth

More info
  • ReceivedJan 18, 2020
  • AcceptedMay 25, 2020
  • PublishedMay 14, 2021

Abstract


Acknowledgment

This work was supported in part by National Key Research and Development Program of China (Grant No. 2018YFB1003203), National Natural Science Foundation of China (Grants No. 61972447), and Fundamental Research Funds for the Central Universities (Grant No. 2019kfyXKJC021). We thank the anonymous reviewers for the helpful comments to improve the presentation of this paper.


References

[1] Diestel R. Graph Theory. 4th ed. Berlin: Springer, 2012. Google Scholar

[2] Bernstein A. A nearly optimal algorithm for approximating replacement paths and $k$ shortest simple paths in general graphs. In: Proceedings of ACM-SIAM symposium on Discrete algorithms (SODA), 2010. 742--755. Google Scholar

[3] Williams V V, Williams R. Subcubic equivalences between path, matrix and triangle problems. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), 2010. 645--654. Google Scholar

[4] Itai A, Rodeh M. Finding a Minimum Circuit in a Graph. SIAM J Comput, 1978, 7: 413-423 CrossRef Google Scholar

[5] Coppersmith D, Winograd S. Matrix multiplication via arithmetic progressions. J Symbolic Computation, 1990, 9: 251-280 CrossRef Google Scholar

[6] Roditty L, Williams V V. Minimum weight cycles and triangles: Equivalences and algorithms. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), 2011. 180--189. Google Scholar

[7] Williams V V. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. In: Proceedings International Programme on the Elimination of Child Labour (IPEC), 2015. 17--29. Google Scholar

[8] Lingas A, Lundell E M. Efficient approximation algorithms for shortest cycles in undirected graphs. Inf Processing Lett, 2009, 109: 493-498 CrossRef Google Scholar

[9] Roditty L, Tov R. Approximating the girth. ACM Trans Algorithms, 2013, 9: 1--13. Google Scholar

[10] Holzer S, Wattenhofer R. Optimal distributed all pairs shortest paths and applications. In: Proceedings of ACM symposium on Principles of distributed computing (PODC), 2012. 355--364. Google Scholar

[11] Lenzen C, Peleg D. Efficient distributed source detection with limited bandwidth. In: Proceedings of ACM symposium on Principles of distributed computing (PODC), 2013. 375--382. Google Scholar

[12] Nanongkai D. Distributed approximation algorithms for weighted shortest paths. In: Proceedings of Symposium on the Theory of Computing (STOC), 2014. 565--573. Google Scholar

[13] Peleg D, Roditty L, Tal E. Distributed algorithms for network diameter and girth. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), 2012. 660--672. Google Scholar

[14] Hua Q, Fan H, Qian L, et al. Brief announcement: a tight distributed algorithm for all pairs shortest paths and applications. In: Proceedings of Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016. 439--441. Google Scholar

[15] Hua Q, Fan H, Ai M, et al. Nearly optimal distributed algorithm for computing betweenness centrality. In: Proceedings of International Conference on Distributed Computing Systems (ICDCS), 2016. 271--280. Google Scholar

[16] Frischknecht S, Holzer S, Wattenhofer R. Networks cannot compute their diameter in sublinear time. In: Proceedings of ACM-SIAM symposium on Discrete algorithms (SODA), 2012. 1150--1162. Google Scholar

[17] Huang C C, Nanongkai D, Saranurak T. Distributed exact weighted all-pairs shortest paths in o(n5=4) rounds. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), 2017. 168--179. Google Scholar

[18] Peleg D. Distributed computing a locality sensitive approach. SIAM Monographs on discrete mathematics and applications, 2000 5. Google Scholar

[19] Elkin M. Distributed exact shortest paths in sublinear time. In: Proceedings of Symposium on the Theory of Computing (STOC), 2017. 757--770. Google Scholar

[20] Leighton F T, Maggs B M, Rao S B. Packet routing and job-shop scheduling inO(congestion+dilation) steps. Combinatorica, 1994, 14: 167-186 CrossRef Google Scholar

[21] Yao A C. Some complexity questions related to distributive computing (preliminary report). In: Proceedings of Symposium on the Theory of Computing (STOC), 1979. 209--213. Google Scholar

[22] Kushilevitz E, Nisan N. Communication Complexity. Cambridge: Cambridge University Press, 1997. Google Scholar

[23] Jin H, Yao P, Liao X. Towards dataflow based graph processing. Sci China Inf Sci, 2017, 60: 126102 CrossRef Google Scholar

qqqq

Contact and support