基于平均度的树分解启发式算法  

Heuristic algorithms of tree decomposition based on average degree

作　　者：沈静[1] 任耀峰[1] 梅丹 杨美妮[1] SHEN Jing;REN Yao-feng;MEI Dan;YANG Mei-ni(Dept. of Basic Courses, Naval Univ. of Engineering, Wuhan 430033, China)

机构地区：[1]海军工程大学基础部

出　　处：《海军工程大学学报》2019年第5期49-53,共5页Journal of Naval University of Engineering

基　　金：国家自然科学基金资助项目(61402516,61370052);海军工程大学自主立项资助项目(20160331)

摘　　要：很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。Many instances of NP-hard problems with small tree width can be solved in polynomial time by tree decomposition, and thus finding the optimal tree width of misdirected graph can improve the solving efficiency. Two new heuristic algorithms for tree decomposition are proposed by average degree of graphs. According to the relationship between tree decomposition and triangulation, the two algorithms use the degree bias and the number of fill-in edges to find an elimination ordering, and quickly gain the width of tree decomposition. The two algorithms are easy to implement. The experimental results of random regular graphs and DIMACS graph coloring instances show that the two algorithms can find better upper bound of tree width compared with min-fill heuristic algorithm.

关 键 词：树宽 树分解 启发式算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]