An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure (Q1073717)

The authors consider a special linear programming problem. Constraints of the problem are in natural correspondence with paths from the root to leaves in a tree. For solving the problem they propose an algorithm with runs in time \(O(n^ 2)\), where n is the number of leaves in the tree. The algorithm has run time O(n log n) for balanced trees.