For Full-Text 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 Non-Terminal Set VNT on Series-Parallel Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/04/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
spanning tree, series-parallel graph, algorithm,
Full Text: PDF(2.3MB)>>
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 a series-parallel graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.