TY - JOUR

T1 - Algorithmic aspects of vertex ellmination

AU - Rose, Donald J.

AU - TarJan, R. Endre

N1 - Funding Information:
Research partially sponsored by the Office of Naval Research under contract NO0014-67-A-0298-O034 at Harvard University, and by the National Science Foundation, Grant GJ-3560X and a Miller Research Fellowship at the University of California, Berkeley. Part of this work was completed while the first author was svisiting the Computer Science Department at the University of Colorado and the second author was visiting the Welzmann Institute of Science, Rehovot, Israel.
Funding Information:
R. Endre TarJan Computer Science Division Department of Electrical Engineering and Computer Sciences Electronics Research Laboratory University of California, Berkeley tResearch partially sponsored by the Office of Naval Research under contract NO0014-67-A-0298-O034 at Harvard University, and by the National Science Foundation, Grant GJ-3560X and a ~ller Research Fellowship at the University of California, Berkeley. Part of this work was completed while the first author was visiting the Computer Science Department at the University of Colorado and the second author was visiting the Welzmann Institute of Science, Rehovot, Israel.

PY - 1975/5/5

Y1 - 1975/5/5

N2 - We consider a graph-theoretic elimination process which is related to performin~ Gaussian elimination on sparse symmetric and unsymmetrlc systems of linear equations. We discuss good al~orlthms for finding elimination orderings, showing that a generalization of breadth-flrst search, called lexicographlc search, can be used to find perfect orderlngs in O(n+e) time and minimal orderlngs in O(ne) time, if the problem graph is undirected and has n vertices and e edges. We also give efficient (though slower) algorithms for generating such orderings on directed graphs. We claim that the minimum ordering problem for directed graphs is NP-complete, and conjecture that it is also NP-complete for undirected graphs. We include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.

AB - We consider a graph-theoretic elimination process which is related to performin~ Gaussian elimination on sparse symmetric and unsymmetrlc systems of linear equations. We discuss good al~orlthms for finding elimination orderings, showing that a generalization of breadth-flrst search, called lexicographlc search, can be used to find perfect orderlngs in O(n+e) time and minimal orderlngs in O(ne) time, if the problem graph is undirected and has n vertices and e edges. We also give efficient (though slower) algorithms for generating such orderings on directed graphs. We claim that the minimum ordering problem for directed graphs is NP-complete, and conjecture that it is also NP-complete for undirected graphs. We include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.

KW - Breadth-flrst search

KW - Directed graph

KW - Gaussian elimination

KW - Graph

KW - Lexicographlc ordering

KW - Perfect elimination

KW - Sparse linear equations

KW - Triangulated graph

UR - http://www.scopus.com/inward/record.url?scp=85014307869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014307869&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85014307869

SP - 245

EP - 254

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0737-8017

T2 - 7th Annual ACM Symposium on Theory of Computing, STOC 1975

Y2 - 5 May 1975 through 7 May 1975

ER -