
For FullText 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 NonTerminal Set V_{NT} on Cographs
Shinichi NAKAYAMA Shigeru MASUYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E99D
No.10
pp.25742584 Publication Date: 2016/10/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2016EDP7021
Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: spanning tree, cograph, algorithm,
Full Text: PDF(1.5MB)>>
Summary:
Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset V_{NT} of vertices called a nonterminal set, the spanning tree with nonterminal set V_{NT} is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a nonterminal 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 nonterminal set V_{NT} of G was known to be NPhard. 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 NPhard 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 nonterminal set V_{NT} of G is linearly solvable when each edge has the weight of one.

