Network Simplex Algorithm. Parallel Solution for Finding the Leaving Arc

Abstract

Starting from the degeneracy in Network Simplex Algorithm appears the problem of finding, and later on keeping a strong feasible spanning tree. Having an initial structure like the one described above, we can maintain the same properties by carefully choosing the leaving arc rule. This rule is using the Lowest Common Ancestor technique for which I propose a parallel solution.