Representing inverses in pure network flow optimization

Abstract

A basis for a pure network flow problem always exhibits special structure, whose exploitation has led to the development of extremely efficient network optimization software. The backbone of these programs is a data structure which represents the basis as a tree and is used to perform the linear algebraic steps required for optimization. We demonstrate that the basis inverse also possesses a special structure which we call the inverse-tree. We develop a data structure to represent the inverse tree, and we show that it obeys a symmetric relationship with the basis-tree data structure. (The predecessor function of the inverse-tree is the preorder link function of the basis-tree and vice versa). We develop efficient computational procedures for exploiting these results and show that using the inverse-tree requires computation of the same order as the basis-tree.