IEICE TRANSACTIONS on Information
Traversing Graphs in Small Space
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.392-396
- Publication Date
- 2000/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- INVITED SURVEY PAPER
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
