The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Diberi graf G=(V, E), di mana V and E ialah set bucu dan tepi daripada G, dan subset VNT daripada bucu yang dipanggil a tidak-terminal menetapkan, voltan pokok bersama a tidak-terminal menetapkan VNT, dilambangkan dengan STNT, ialah subgraf rentangan bersambung dan akiklik bagi G yang mengandungi semua bucu V di mana setiap bucu dalam set bukan terminal bukan daun. Pada graf umum, masalah mencari STNT bagi G dikenali sebagai NP-hard. Dalam kertas ini, kami menunjukkan bahawa jika G ialah graf lengkok bulat kemudian mencari STNT bagi G boleh diselesaikan secara polinomial berkenaan dengan bilangan bucu.
Shin-ichi NAKAYAMA
Tokushima University
Shigeru MASUYAMA
Tokyo University of Science
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.
Salinan
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
Salinan
@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},}
Salinan
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 -