摘要
文[1]从算法复杂性的估计中提出一个图的最优标号(排序)问题-顶点的最优消去问题.本文将给出若干基本的理论结果,其中包含NP-完全性、上下界、与其它目论参数的关系及特殊图结果等.
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.
出处
《系统科学与数学》
CSCD
北大核心
1997年第4期354-361,共8页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金
山西省自然科学基金
关键词
消去顺序
分解定理
图
最优标号
最优消去问题
Graph labelling, elimination order, nuclear density, decomposition theorem
