A space lower bound for st-connectivity on node-named JAGs

DOI10.1016/S0304-3975(00)00019-0MaRDI QIDQ1566733zbMATH OpenOpenAlexFDO

Authors Chung Keung Poon

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(00)00019-0

zbMATH Keywords

complexityconnectivitygraphlower boundspace

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1263190
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• scientific article; zbMATH DE number 1559538
• Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models

Cites work

• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
• Computational Complexity of Probabilistic Turing Machines
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1414308 (Why is no real title available?)
• Maze recognizing automata and nondeterministic tape complexity
• Nondeterministic Space is Closed under Complementation
• Relationships between nondeterministic and deterministic tape complexities
• Space Lower Bounds for Maze Threadability on Restricted Machines
• The method of forced enumeration for nondeterministic automata
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• Time-space trade-offs for undirected st-connectivity on a JAG

Cited in

(6)

• Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models
• scientific article; zbMATH DE number 1263190 (Why is no real title available?)
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• A Formalised Lower Bound on Undirected Graph Reachability
• Algorithms and Computation
• Simulating time with square-root space

This page was built for publication: A space lower bound for \(st\)-connectivity on node-named JAGs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1566733)