Algorithmic aspects of vertex ellmination

Donald J. Rose, R. Endre TarJan

Research output: Contribution to journalConference articlepeer-review

46 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)245-254
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - May 5 1975
Externally publishedYes
Event7th Annual ACM Symposium on Theory of Computing, STOC 1975 - Albuquerque, United States
Duration: May 5 1975May 7 1975

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Breadth-flrst search
  • Directed graph
  • Gaussian elimination
  • Graph
  • Lexicographlc ordering
  • Perfect elimination
  • Sparse linear equations
  • Triangulated graph

Fingerprint

Dive into the research topics of 'Algorithmic aspects of vertex ellmination'. Together they form a unique fingerprint.

Cite this