
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 LinearTime Algorithm for Finding a Spanning Tree with NonTerminal Set V_{NT} on Interval Graphs
Shinichi NAKAYAMA Shigeru MASUYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E101D
No.9
pp.22352246 Publication Date: 2018/09/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2018EDP7047
Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: spanning tree, interval graph, algorithm,
Full Text: PDF(1.2MB)>>
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. The complexity of finding a spanning tree with nonterminal set V_{NT} on general graphs where each edge has the weight of one is known to be NPhard. In this paper, we show that if G is an interval graph then finding a spanning tree with a nonterminal set V_{NT} of G is linearlysolvable when each edge has the weight of one.

