%0 Journal Article
%T MIN-MAX ELIMINATION ORDER PROBLEM FOR GRAPHS<br>图的min-max型最优消去顺序问题
%A Yang Aimin
%A <br>杨爱民
%J 系统科学与数学
%D 1997
%I 
%X 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.
%K Graph labelling
%K elimination order
%K nuclear density
%K decomposition theorem<br>图标号
%K 消去顺序
%K 核密度
%K 分解定理
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=6E709DC38FA1D09A4B578DD0906875B5B44D4D294832BB8E&cid=37F46C35E03B4B86&jid=0CD45CC5E994895A7F41A783D4235EC2&aid=2B5843AE6556902309DA4C4720815352&yid=5370399DC954B911&vid=BCA2697F357F2001&iid=E158A972A605785F&sid=0954045FA0C6885F&eid=3E3EF0DB5E6F2DA9&journal_id=1000-0577&journal_name=系统科学与数学&referenced_num=6&reference_num=0