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
Dado um gráfico G=(V,E) Onde V e E são um conjunto de vértices e arestas, respectivamente, especificados com um subconjunto VNT de vértices chamados não-terminal conjunto, a árvore geradora com conjunto não terminal VNT é um subgrafo abrangente conectado e acíclico de G que contém todos os vértices de V onde cada vértice em um conjunto não terminal não é uma folha. A complexidade de encontrar uma árvore geradora com conjunto não terminal VNT em gráficos gerais onde cada aresta tem o peso de um é conhecido por ser NP-difícil. Neste artigo, mostramos que se G é um gráfico de intervalo e então encontra uma árvore geradora com um conjunto não terminal VNT of G é linearmente solucionável quando cada aresta tem o peso de um.
Shin-ichi NAKAYAMA
Tokushima University
Shigeru MASUYAMA
Toyohashi University of Technology
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.
Copiar
Shin-ichi NAKAYAMA, Shigeru MASUYAMA, "A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 9, pp. 2235-2246, September 2018, doi: 10.1587/transinf.2018EDP7047.
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. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph 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.2018EDP7047/_p
Copiar
@ARTICLE{e101-d_9_2235,
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 Interval Graphs},
year={2018},
volume={E101-D},
number={9},
pages={2235-2246},
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. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph 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.2018EDP7047},
ISSN={1745-1361},
month={September},}
Copiar
TY - JOUR
TI - A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2235
EP - 2246
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2018
DO - 10.1587/transinf.2018EDP7047
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2018
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. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph 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 -