Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

AbstractThis paper considers the problem of finding a minimal triangulation of an undirected graph G = (V, E), where a triangulation is a set T such that every cycle in G = (V, E ∪ T) has a chord. A triangulation T is minimal (minimum) if no triangulation F exists such that F is a proper subset of T (¦F¦ < ¦T¦), and an ordering α is optimal (optimum) if a minimal (minimum) triangulation is generated by α. A minimum triangulation (optimum ordering) is necessarily minimal (optimal), but the converse is not necessarily true. A necessary and sufficient condition for a triangulation to be minimal is presented. This leads to an algorithm for finding an optimal ordering α which produces a minimal set of “fill-in” when the process is viewed as triangular factorization of a sparse matrix