限制树宽的图的最小标记生成数算法

摘要：

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。

关键词： 最小标记生成树 搜索树 限制树宽 确定参数可解

作者: 徐忆晨 Rudolf Fieischer

作者单位: 复旦大学智能信息处理上海重点实验室,上海,200433 复旦大学计算机科学与工程系,上海,200433

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 72-74

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）