scientific article; zbMATH DE number 1256637

zbMath0915.05081MaRDI QIDQ4230323

Avi Wigderson, Endre Szemerédi, Noam Nisan

Publication date: 22 April 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

deterministic algorithmconnectivity problem on undirected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (7)

Universal traversal sequences with backtracking. ⋮ The complexity of planarity testing ⋮ An unambiguous class possessing a complete set ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Improved algorithms via approximations of probability distributions

This page was built for publication: