2 papers
cs.DS2024
Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
Vignesh Manoharan, Vijaya Ramachandran
Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in a graph . This is a fundamental graph problem with classical sequential algorithms…
cs.DS2024
Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
Vignesh Manoharan, Vijaya Ramachandran
We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these…