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)