Publication:4230323

zbMath0915.05081MaRDI QIDQ4230323

Endre Szemerédi, Avi Wigderson, Noam Nisan

Publication date: 22 April 1999

zbMATH Keywords

deterministic algorithm; connectivity problem on undirected graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

05C40: Connectivity

Related Items

Pseudorandom generators for combinatorial checkerboards, Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\))., Improved algorithms via approximations of probability distributions, Universal traversal sequences with backtracking., The complexity of planarity testing