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

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

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