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

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.

Key words: minimum label spanning tree, search tree, bounded treewidth, fixed-parameter tractablility