MIN-MAX ELIMINATION ORDER PROBLEM FOR GRAPHS
图的min-max型最优消去顺序问题

The optimal elimination order problem for graphs, was raised from the algorithmic complexity evaluation by 1]. This is to determine an optimal vertex order so that the maximum frontage of eliminated venices is minimized. This paper presents some fundamental theoretical results on this problem, including lower and upper bounds, NP-completeness, and relations with other graph-theoretic parameters. Finally, decomposition theorems and several exact results for special graphs are obtained.