Helmut Alt
Kurt Mehlhorn
- H. Alt & K. Mehlhorn: Untere Schranken füür den Platzbedarf bei der kontext-freien Analyse, Techn. Bericht, Fachbereich 10 der Universitat des Saarlandes, 1975Google Scholar
- J. Hopcroft & J. Ullman: Formal Languages and their Reläätion to Automata, Addison-Wesley, Reading, Mass., 1969 Google ScholarDigital Library
Recommendations
An O(log n log log n) space algorithm for undirected st-connectivity
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Koucký [13]. Our ...
Fully dynamic connectivity in O(log n(log log n)2) amortized expected time
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsDynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)2) amortized expected update time and O(log n/log log log n) query time, which ...
Finding Connected Components in O(log n log log n) Time on the EREW PRAM
In this paper, a parallel algorithm for finding the connected components of an undirected graph is presented. On a graph with n vertices and m edges, the algorithm runs in O(log n log log n) time using n + m processors on an EREW (exclusive-read and ...
Comments