A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc 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, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.8 pp.1373-1382
- Publication Date
- 2022/08/01
- Publicized
- 2022/05/12
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021EDP7175
- 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 Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 8, pp. 1373-1382, August 2022, doi: 10.1587/transinf.2021EDP7175.
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, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7175/_p
Copy
@ARTICLE{e105-d_8_1373,
author={Shin-ichi NAKAYAMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs},
year={2022},
volume={E105-D},
number={8},
pages={1373-1382},
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, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.},
keywords={},
doi={10.1587/transinf.2021EDP7175},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1373
EP - 1382
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2022
DO - 10.1587/transinf.2021EDP7175
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2022
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, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.
ER -
English
