| 限制树宽的图的最小标记生成数算法 |
| |
| 引用本文： | 徐忆晨.限制树宽的图的最小标记生成数算法[J].计算机工程与科学,2008,30(12):72-74. |
| |
| 作者姓名： | 徐忆晨 |
| |
| 作者单位： | 复旦大学智能信息处理上海重点实验室,上海,200433;复旦大学计算机科学与工程系,上海,200433 |
| |
| 基金项目： | 国家自然科学基金资助项目，上海重点学科建设基金资助项目，The Robert Bosch Foundation |
| |
| 摘 要： | 本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法；然后考虑了限制树宽的图，得到了效率更高的算法。该算法在树宽为常数的情况下，时间复杂度关于图的顶点个数为多项式，从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。
|
| 关 键 词： | 最小标记生成树 搜索树 限制树宽 确定参数可解 |
The Minimum Label Spanning Tree Algorithm for the Graph of Bounded Treewidth |
| |
| XU Yi-chen,Rudolf Fieischer.The Minimum Label Spanning Tree Algorithm for the Graph of Bounded Treewidth[J].Computer Engineering & Science,2008,30(12):72-74. |
| |
| Authors: | XU Yi-chen Rudolf Fieischer |
| |
| Abstract: | This paper studies the minimal label spanning tree problem of graphs.First we introduce this problem on the general graphs.Then we focus on the minimal label spanning tree problem of the graphs of bounded treewidth.In this paper,we get an algorithm which is polynomial on the size of graph,showing that this problem is fixed-parameter tractable. |
| |
| Keywords: | minimum label spanning tree search tree bounded treewidth fixed-parameter tractablility |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
