IMADA

Abstract (Gregory Gutin)

We show that the problem of detecting an embedded network in a linear program is closely related to balanced signed graphs previously used in other applications. It leads to a simple linear time algorithm to recognize linear programs which can be transformed into pure networks by a sequence of row reflections. This algorithm can be used as a heuristic for extracting embedded networks in linear programs.
Last modified: March 13, 1998.
Kim Skak Larsen (kslarsen@imada.sdu.dk)