A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set V_NT on Series-Parallel Graphs

摘要

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 non -terminal set , the minimum spanning tree with a non -terminal 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 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.