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

The Minimum Label Spanning Tree Algorithm for the Graph of Bounded Treewidth

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

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.