|
|||||
|
|
| 基于平均度的树分解启发式算法 | |
| 作者姓名： | 沈静 任耀峰 梅丹 杨美妮 |
| 作者单位： | 海军工程大学 基础部,武汉,430033;海军工程大学 基础部,武汉,430033;海军工程大学 基础部,武汉,430033;海军工程大学 基础部,武汉,430033 |
| 基金项目： | 国家自然科学基金;国家自然科学基金;海军工程大学自主立项资助项目 |
| 摘 要： | 很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。 |
| 关 键 词： | 树宽 树分解 启发式算法 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |