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

Traversing Graphs in Small Space Percorrendo gráficos em espaços pequenos

Seinosuke TODA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Esboçamos dois algoritmos que resolvem o problema não direcionado st-problema de conectividade em uma pequena quantidade de espaço. Um deles fica por conta de Nisan, Szemeredy e Wigderson, e ocupa espaço O(registro3/2n), Onde n denota o número de nós em um determinado gráfico não direcionado. Este é o primeiro algoritmo que superou a barreira de Savitch na complexidade espacial do problema. A outra é devida a Tarui e a este autor, e ocupa espaço O(sw(G)2 log2 n), onde sw(G) denota a largura de separação de um determinado gráfico G. O seu resultado implica que o st-o problema de conectividade pode ser resolvido no espaço logarítmico para qualquer classe de grafos com largura de separação limitada acima por uma constante predeterminada. Esta classe é uma das poucas classes não triviais para as quais o st-o problema de conectividade pode ser resolvido no espaço logarítmico.

Publicação
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.392-396
Data de publicação
2000/03/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
INVITED SURVEY PAPER
Categoria
Algoritmos de gráfico

autores

Palavra-chave