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.
Publisher Copyright:
© 1975 Association for Computing Machinery. All rights reserved.
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
SN - 0737-8017
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
T2 - 7th Annual ACM Symposium on Theory of Computing, STOC 1975
Y2 - 5 May 1975 through 7 May 1975
ER -