A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs Um algoritmo de tempo linear para encontrar uma árvore geradora com conjunto não terminal VNT em gráficos de intervalo

Shin-ichi NAKAYAMA, Shigeru MASUYAMA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E101-D No.9 pp.2235-2246
Data de publicação
2018/09/01
Publicitada
2018/06/18
ISSN online
1745-1361
DOI
10.1587/transinf.2018EDP7047
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

Shin-ichi NAKAYAMA
  Tokushima University
Shigeru MASUYAMA
  Toyohashi University of Technology

Palavra-chave