Maximal chordal subgraphs (Q1115455)

A graph G is chordal if it does not contain any cycle of length greater than 3 as an induced subgraph. The authors thoroughly motivate the study of chordal graphs. An algorithm for finding a maximal chordal subgraph of an arbitrary graph G is presented. It is shown that this algorithm can be implemented with a worst-case time complexity bound of 0(\(| E| \Delta)\) where \(\Delta\) is the maximum degree among the vertices of G. It is then shown that the maximum independent set problem can be formulated using maximal chordal subgraphs. It is pointed out that this formulation is stronger than the customary edge-vertex formulation and leads to a Lagrangian relaxation approach. The authors then show how maximal chordal subgraphs can be used to define a splitting for the coefficient matrix of a large sparse system of linear equations. This splitting is then used to produce iterative schemes for solving the original system of equations.