Algorithmic aspects of vertex elimination on directed graphs.

[摘要] 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.

[学科分类] 计算机科学（综合）