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
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.
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
Seinosuke TODA, "Traversing Graphs in Small Space" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 392-396, March 2000, doi: .
Abstract: We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_392/_p
Copiar
@ARTICLE{e83-d_3_392,
author={Seinosuke TODA, },
journal={IEICE TRANSACTIONS on Information},
title={Traversing Graphs in Small Space},
year={2000},
volume={E83-D},
number={3},
pages={392-396},
abstract={We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.},
keywords={},
doi={},
ISSN={},
month={March},}
Copiar
TY - JOUR
TI - Traversing Graphs in Small Space
T2 - IEICE TRANSACTIONS on Information
SP - 392
EP - 396
AU - Seinosuke TODA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.
ER -