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

DOI10.1016/S0304-3975(00)00019-0zbMath0943.68125OpenAlexW2010962367MaRDI QIDQ1566733

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

complexitygraphconnectivitylower boundspace

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Maze recognizing automata and nondeterministic tape complexity
• Relationships between nondeterministic and deterministic tape complexities
• Nondeterministic Space is Closed under Complementation
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Computational Complexity of Probabilistic Turing Machines
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• Time-space trade-offs for undirected st-connectivity on a JAG

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