Tight Lower Bounds for st-Connectivity on the NNJAG Model

DOI10.1137/S0097539795295948zbMath0943.68069MaRDI QIDQ4268867

Chung Keung Poon, Jeff Edmonds, Demetrios Achlioptas

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

connectivitylower boundsspace complexityspace-time tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (9)

Formulas versus Circuits for Small Distance Connectivity ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ Pure Pointer Programs with Iteration ⋮ Incremental branching programs ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs

This page was built for publication: Tight Lower Bounds for st-Connectivity on the NNJAG Model