For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on CographsShin-ichi NAKAYAMA  Shigeru MASUYAMA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.10   pp.2574-2584Publication Date: 2016/10/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.2016EDP7021 Type of Manuscript: PAPERCategory: Fundamentals of Information SystemsKeyword: spanning tree,  cograph,  algorithm,  Full Text: PDF>> Buy this Article Summary:  Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.