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 Space-Efficient Separator Algorithm for Planar Graphs Um algoritmo separador com eficiência de espaço para gráficos planares

Ryo ASHIDA, Sebastian KUHNERT, Osamu WATANABE

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Miller [9] propôs um algoritmo de tempo linear para calcular pequenos separadores para grafos planares 2 conectados. Explicamos seu algoritmo e apresentamos uma maneira de modificá-lo para uma versão com eficiência de espaço. Nosso algoritmo pode ser considerado como uma redução do espaço logarítmico desde a construção do separador até a construção da primeira árvore de busca em largura.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1007-1016
Data de publicação
2019/09/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E102.A.1007
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Algoritmos de gráficos

autores

Ryo ASHIDA
  Tokyo Institute of Technology
Sebastian KUHNERT
  Humboldt University of Berlin
Osamu WATANABE
  Tokyo Institute of Technology

Palavra-chave