BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-531
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Algorithmic aspects of vertex elimination on directed graphs.
        TYPE:: Technical Report
      AUTHOR:: Rose, Donald J.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: November 1975
       PAGES:: 45
    ABSTRACT:: We consider a graph-theoretic elimination process which is
               related to performing Gaussian elimination on sparse systems
               of linear eauations. We give efficient algorithms to:

               (1) calculate the fill-in produced by any elimination
               ordering;

               (2) find a perfect elimination ordering if one exists; and

               (3) find a minimal elimination ordering.

               We also show that problems (1) and (2) are at least as
               time-consuming as testing whether a directed graph is
               transitive, and that the problem of finding a minimum
               ordering is NP-complete.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-531