We provide algorithms performing Depth-First Search (DFS) on a directed or undirected
graph with n vertices and m edges using only O (n) bits. One algorithm uses O (n) bits and …

Back in 1964 Williams introduced the binary heap as a basic priority queue data structure
supporting the operations Insert and ExtractMin in logarithmic time. Since then numerous …

We revisit the read-only random-access model, in which the input array is read-only and a
limited amount of workspace is allowed. Given a set of N two-dimensional points in a read …

We consider the classical selection and sorting problems in a model where the initial
permutation of the input has to be restored after completing the computation. While the …

Given an unordered array of N elements drawn from a totally ordered set and an integer k in
the range from 1 to N, in the classic selection problem the task is to find the k-th smallest …

We consider the classical selection and sorting problems in a model where the initial
permutation of the input has to be restored after completing thecomputation. Such algorithms …

A c-color choice dictionary of size n in N is a fundamental data structure in the development
of space-efficient algorithms that stores the colors of n elements and that supports …

Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with
vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that all …

We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It
is assumed that the input is in a read-only array of $ n $ items and that the available …

Given a sequence of integers, we want to find a longest increasing subsequence of the
sequence. It is known that this problem can be solved in O (n log n) time and space. Our …