The Complexity of Distributed Minimum Weight Cycle Approximation

Yi-Jun Chang, Yanyu Chen, Dipan Dey +4

We study the Minimum Weight Cycle (MWC) problem in the $\mathsf{CONGEST}$ model of distributed computing. For undirected weighted graphs, we give a randomized $(k+1)$-approximation…