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

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.3   pp.434-443
Publication Date: 2017/03/01
Publicized: 2016/12/21
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016FCP0010
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
spanning tree,  outerplanar graph,  algorithm,  

Full Text: PDF>>
Buy this Article

Given a graph G=(V, E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, the minimum spanning tree with a non-terminal set VNT, denoted by MSTNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V with the minimum weight where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an MSTNT of G is NP-hard. We show that if G is an outerplanar graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.