A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Cographs
Summary :
Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.
- Publication
- IEICE TRANSACTIONS on Information Vol.E99-D No.10 pp.2574-2584
- Publication Date
- 2016/10/01
- Publicized
- 2016/07/12
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016EDP7021
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
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 Spanning Tree with Non-Terminal Set VNT on Cographs" in IEICE TRANSACTIONS on Information,
vol. E99-D, no. 10, pp. 2574-2584, October 2016, doi: 10.1587/transinf.2016EDP7021.
Abstract: Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7021/_p
Copy
@ARTICLE{e99-d_10_2574,
author={Shin-ichi NAKAYAMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Cographs},
year={2016},
volume={E99-D},
number={10},
pages={2574-2584},
abstract={Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.},
keywords={},
doi={10.1587/transinf.2016EDP7021},
ISSN={1745-1361},
month={October},}
Copy
TY - JOUR
TI - A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Cographs
T2 - IEICE TRANSACTIONS on Information
SP - 2574
EP - 2584
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2016
DO - 10.1587/transinf.2016EDP7021
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2016
AB - Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.
ER -
English
