摘要
本文从一个离散最优化问题的算法复杂性出发,提出了图论中一个新的而有趣的问题:图的节点最优消除顺序.这一问题不仅有实用价值,而且有理论意义.本文只得到该问题的部分结果,并提出了若干待解决的问题,供有兴趣的读者进行研究.
In a class of numerical computation problems,the complexity of an algorithm depends onthe order of variables eliminated.The optimal order of variables eliminated is the one thatmakes the complexity as low as possible.This paper presents a method that formulates an order of variables to be eliminated as theorder of nodes to be deleted from a graph,and gives two heuristic algorithms for finding agood order of nodes to be deleted from a graph.Finally,some open problems are proposed forfurther study.
出处
《系统科学与数学》
CSCD
北大核心
1992年第4期307-316,共10页
Journal of Systems Science and Mathematical Sciences
