IEICE TRANSACTIONS on Information
A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Outerplanar 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 an outerplanar graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.
- Publication
- IEICE TRANSACTIONS on Information 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 —)
- Category
Authors
Shin-ichi NAKAYAMA
Tokushima University
Shigeru MASUYAMA
Toyohashi University of Technology
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 Outerplanar Graphs" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 3, pp. 434-443, March 2017, doi: 10.1587/transinf.2016FCP0010.
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 an outerplanar 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.2016FCP0010/_p
Copy
@ARTICLE{e100-d_3_434,
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 Outerplanar Graphs},
year={2017},
volume={E100-D},
number={3},
pages={434-443},
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 an outerplanar graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.},
keywords={},
doi={10.1587/transinf.2016FCP0010},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Outerplanar Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 434
EP - 443
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2017
DO - 10.1587/transinf.2016FCP0010
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2017
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 an outerplanar graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.
ER -
English
