Graph triangulation

I am using METIS as a tool for graph triangulation. For sparse matrix computations, one wishes to find an ordering of the matrix that minimizes the amount of fill in the matrix. The fill can also be viewed as the number of edges in the triangulated graph. I would like to find an ordering that minimizes the size of the largest clique in the triangulated graph. Some experiments with METIS's ordering routines have demonstrated that multiple minimum degree typically finds orderings that outperform the nested dissection routines in terms of this largest clique metric.

Has anyone else used METIS for this purpose, or does anyone have suggestions on how to tweak certain parameters to find "good" orderings with respect to the minimization of the max clique size? Thanks

Chris Groer