In his paper "Scaling Algorithms for Network Problems", Harold Gabow details several algorithms for graph problems that work using scaling, iteratively refining a candidate answer by beginning with a low-precision approximation to the original problem and repeatedly increasing the precision. One of the problems that he considers is the single-source shortest paths problem with nonnegative weights, giving an algorithm that works through iterated applications of Dijkstra's algorithm in a modified graph.

I have seen this technique used in other places (min-cost max-flow, sorting, etc.), but one combinatorial problem that I have not seen solved via scaling is the minimum spanning tree problem. Given the relation between Dijkstra's algorithm and Prim's algorithm, combined with the paper's discussion of a scaling implementation of Dijkstra's algorithm, it seems like there may be an efficient algorithm of this sort.

Has this problem been studied in any depth? If so, are there any resources or papers I should take a look at? If not, does anyone have any suggestions for how an efficient algorithm of this sort could be attempted?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.