Scaling algorithms for network problems (Q1079135)

The network problems as, e.g., minimum spanning tree, bottleneck shortest path, shortest path with nonnegative lengths and shortest path with arbitrary lengths, maximum network flow, minimum cost flow in a network with unit capacities, maximum weight matching in bipartite graphs and degree-constrained subgraph can be solved by scaling the numeric parameters of a given edge-weighted graph. An algorithm for scaling is proposed such that its application gives a method being superior to the traditional ones. The numerical complexities of the best known traditional algorithms are compared with those derived here for scaling algorithms.