
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 Minimum Spanning Tree with NonTerminal Set V_{NT} on Outerplanar Graphs
Shinichi NAKAYAMA Shigeru MASUYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E100D
No.3
pp.434443 Publication Date: 2017/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2016FCP0010
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —) Category: Keyword: spanning tree, outerplanar graph, algorithm,
Full Text: PDF(1.1MB)>>
Summary:
Given a graph G=(V, E), where V and E are vertex and edge sets of G, and a subset V_{NT} of vertices called a nonterminal set, the minimum spanning tree with a nonterminal set V_{NT}, 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 nonterminal set is not a leaf. On general graphs, the problem of finding an MSTNT of G is NPhard. 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.

