A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.9   pp.2235-2246
Publication Date: 2018/09/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7047
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
spanning tree,  interval graph,  algorithm,  

Full Text: PDF(1.2MB)>>
Buy this Article

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. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph then finding a spanning tree with a non-terminal set VNT of G is linearly-solvable when each edge has the weight of one.