| 概要 |
In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset V_<NT> of vertices as an internal vertex. This problem, called Minimum Weight ...Non-Terminal Spanning Tree, includes s-t Hamiltonian Path as a special case, and hence it is NP-hard. In this paper, we first observe that Non-Terminal Spanning Tree, the unweighted counterpart of Minimum Weight Non-Terminal Spanning Tree, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique-width. In contrast, we give a 3k-vertex kernel and O^∗(2^k)-time algorithm, where k is the size of non-terminal set V_<NT>. The latter algorithm can be extended to Minimum Weight Non-Terminal Spanning Tree with the restriction that each edge has a polynomially bounded integral weight. We also show that Minimum Weight Non-Terminal Spanning Tree is fixed-parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set V_<NT>, extending the fixed-parameter tractability of Minimum Weight Non-Terminal Spanning Tree to the general case. Finally, we give several results for structural parameterization.続きを見る
|
Mendeley出力
