A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.4 pp.826-835
- Publication Date
- 2019/04/01
- Publicized
- 2019/01/25
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018EDP7232
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Shin-ichi NAKAYAMA
Tokushima University
Shigeru MASUYAMA
Tokyo University of Science
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shin-ichi NAKAYAMA, Shigeru MASUYAMA, "A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 4, pp. 826-835, April 2019, doi: 10.1587/transinf.2018EDP7232.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7232/_p
Copy
@ARTICLE{e102-d_4_826,
author={Shin-ichi NAKAYAMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs},
year={2019},
volume={E102-D},
number={4},
pages={826-835},
abstract={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.},
keywords={},
doi={10.1587/transinf.2018EDP7232},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 826
EP - 835
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2019
DO - 10.1587/transinf.2018EDP7232
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2019
AB - 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.
ER -
English
