Algorithmic Aspects of Vertex Elimination on Directed Graphs Export

@article{citeulike:912071, abstract = {We consider a graph-theoretic elimination process which models Gaussian elimination on sparse systems of linear equations. We describe this process by constructive theoretical results which lead to efficient algorithms to 1) compute the fill-in produced by any elimination ordering; 2) find a perfect elimination ordering if one exists; and 3) reduce any fill-in to a minimal fill-in. We relate the complexity of these elimination problems to other well-studied problems by showing that tasks 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.}, author = {Rose, Donald J. and Tarjan, Robert E.}, citeulike-article-id = {912071}, citeulike-linkout-0 = {http://www.jstor.org/stable/2100866}, journal = {SIAM Journal on Applied Mathematics}, keywords = {algorithms, chordal\_graphs, graph\_theory}, number = {1}, pages = {176--197}, posted-at = {2006-10-25 00:35:55}, priority = {2}, title = {Algorithmic Aspects of Vertex Elimination on Directed Graphs}, url = {http://www.jstor.org/stable/2100866}, volume = {34}, year = {1978} }

TY - JOUR ID - citeulike:912071 L3 - citeulike-article-id:912071 N2 - We consider a graph-theoretic elimination process which models Gaussian elimination on sparse systems of linear equations. We describe this process by constructive theoretical results which lead to efficient algorithms to 1) compute the fill-in produced by any elimination ordering; 2) find a perfect elimination ordering if one exists; and 3) reduce any fill-in to a minimal fill-in. We relate the complexity of these elimination problems to other well-studied problems by showing that tasks 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. IS - 1 JF - SIAM Journal on Applied Mathematics EP - 197 TI - Algorithmic Aspects of Vertex Elimination on Directed Graphs VL - 34 SP - 176 KW - algorithms KW - chordal_graphs KW - graph_theory AU - Rose, Donald AU - Tarjan, Robert PY - 1978/// UR - http://www.jstor.org/stable/2100866 ER -