DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                     Extracting Pure Network Submatrices                     
                    in Linear Programs using Signed Graphs                   

                                Gregory Gutin                                
                   Department of Mathematics and Statistics                  
                              Brunel University                              

                      Tuesday, April 7, 1998, at 2:15 PM                     
                               The Seminar Room                              


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.


                                                          Jørgen Bang-Jensen