Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation FactorsResearch Paper
The weighted girth of an undirected graph is the minimum total edge weight of a cycle. Computing this quantity asks for the least expensive closed route with no repeated intermediate vertex or edge. Approximation algorithms trade precision for running time: instead of finding the minimum exactly, they return a number within a specified multiplicative…