Time- and Communication-Efficient Overlay Network Construction via Gossip
(2023)
Conference Proceeding
Dufoulon, F., Moorman, M., Moses Jr., W. K., & Pandurangan, G. (in press). Time- and Communication-Efficient Overlay Network Construction via Gossip. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) (42:1-42:23). https://doi.org/10.4230/LIPIcs.ITCS.2024.42
Efficient live exploration of a dynamic ring with mobile robots (2023)
Journal Article
Mandal, S., Molla, A. R., & Moses Jr., W. K. (2023). Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science, 980, Article 114201. https://doi.org/10.1016/j.tcs.2023.114201The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important require... Read More about Efficient live exploration of a dynamic ring with mobile robots.
Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots (2023)
Conference Proceeding
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2023). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (47-57). https://doi.org/10.1109/IPDPS54959.2023.00015Over the years, much research involving mobile computational entities has been performed. From modeling actual microscopic (and smaller) robots, to modeling software processes on a network, many important problems have been studied in this context. G... Read More about Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots.
Distributed MIS in O(log log n) Awake Complexity (2023)
Conference Proceeding
Dufoulon, F., Moses Jr., W. K., & Pandurangan, G. (2023). Distributed MIS in O(log log n) Awake Complexity. In A. Nolin (Ed.), . https://doi.org/10.1145/3583668.3594574Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have O(log n) round complexity on genera... Read More about Distributed MIS in O(log log n) Awake Complexity.