We consider space-bounded computations on a random-access machine, where the input is given on a read-only random-access medium, the output is to be produced to a write-only sequential-access medium, and the available workspace allows random reads and writes but is of limited capacity. The length of the input is N elements, the length of the output is limited by the computation, and the capacity of the workspace is O ( S ) bits for some predetermined parameter S ≥ lg N . We present a state-of-the-art priority queue—called an adjustable navigation pile —for this restricted model. This priority queue supports M inimum in O (1) time, C onstruct in O ( N ) time, and E xtract - min in O ( N / S + lg S ) time for any S ≥ lg N . The priority queue can be further augmented in O ( N ) time to deal with a batch of at most S elements in a specified range of values at a time, and allow to I nsert (activate) or E xtract (deactivate) an element among these elements, such that I nsert and E xtract take O ( N / S + lg S ) time for any S ≥ lg N . We show how to use our data structure to sort N elements and to compute the convex hull of N points in the Euclidean plane in O ( N 2 / S + N lg S ) time for any S ≥ lg N . Following a known lower bound for the space-time product of any branching program for finding unique elements, both our sorting and convex-hull algorithms are optimal. The adjustable navigation pile has turned out to be useful when designing other space-efficient algorithms, and we expect that it will find its way to yet other applications.

Abstract In this article we propose a new single‐source shortest‐path algorithm that achieves the same O(n · m) time bound as the Bellman‐Ford‐Moore algorithm but outperforms it and other state‐of‐the‐art algorithms in many cases in practice. Our claims are supported by experimental evidence.

We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in-place heap-construction algorithm that runs in Θ(N) worst-case time and performs at most 1.625N+o(N) element comparisons, 1.5N+o(N) element moves, N/B+O(N/M·lgN) cache misses, and 1.375N+o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their algorithm requires Θ(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Θ(N/S) such that each of its leaves root a bottom tree of size Θ(S)⁠. When S=Θ(lgN/lglgN)⁠, we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd's sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice.

We give a variant of the pairing heaps that achieves the following amortized costs: O (1) per find-min and insert , O (log log n ) per decrease-key and meld , O (log n ) per delete-min ; where n is the number of elements in the resulting heap on which the operation is performed. These bounds are the best known for any self-adjusting heap and match two lower bounds, one established by Fredman and the other by Iacono and Özkan, for a family of self-adjusting heaps that generalizes the pairing heaps but do not include our variant. We further show how to reduce the amortized cost for meld to be paid by the other operations, on the expense of increasing that of delete-min to O (log n + log log N ), where N is the total number of elements in the collection of heaps of the data structure (not just the heap under consideration by the operation).

In this paper, we propose a scalable algorithm for finding the exact solution to the maximum-clique problem. At the heart of our approach lies a multi-phase partitioning strategy, which enables iterative, in-memory processing of graphs. The multi-phase partitioning is tuned for the resources of the machine/cluster to get the best performance. To promote parallelization and scalability on both a cluster-level (distributing the problem on a number of machines) and on a machine-level (using all available cores on each machine), we use Apache Spark. We explore the untraditional usage of distributed frameworks, such as Apache Spark, to distribute computational load, as opposed to distributing big data. We focus on dense graphs, typically with thousands of vertices and a few millions edges; this is in contrast to sparse real-world graphs that don't initially fit into the memory of a single driver machine. Our experiments show that, for large dense graphs, we get up to 100% performance speedup compared to the state-of-the-art parallel approaches. Moreover, our algorithm is highly scalable and fault-tolerant.

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 workspace is Theta(s) bits, where lg n <= s <= n * lg n. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of n points that runs in O(n^2 /s + n * lg s) time. We also give a simple algorithm to enumerate the intersections of n line segments that runs in O((n^2 /s^{2/3}) * lg s + k) time, where k is the number of intersections. The counting version can be solved in O((n^2/s^{2/3}) * lg s) time. When the segments are axis-parallel, we give an O((n^2/s) * lg^{4/3} s + n^{4/3} * lg^{1/3} n)-time algorithm that counts the intersections and an O((n^2/s) * lg s * lg lg s + n * lg s + k)-time algorithm that enumerates the intersections, where k is the number of intersections. We finally present an algorithm that runs in O((n^2 /s + n * lg s) * sqrt{(n/s) * lg n}) time to calculate Klee's measure of axis-parallel rectangles.

We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.

We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O ( S + w ) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue—called an adjustable navigation pile—for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O (1) worst-case time and extract in \(O(N/S + \lg S)\) worst-case time, where \(\lg N \leq S \leq N/\lg N\) . We also show how to use this data structure to simplify the existing optimal \(O(N^2/S + N \lg S)\) -time sorting algorithm for this model. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps. Namely, our heap structure requires O(1) for insert and find-min, O(log n) for delete-min, and O(log log n) for decrease-key and meld (all the bounds are in the amortized sense except for find-min).

We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of O (1) per minimum finding and insertion, and the worst-case cost of O (log n ) with at most log n + O (1) element comparisons per deletion, improving the bound of 2 log n + O (1) known for binomial queues. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals log 2 (max {2, n}). As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having n elements and I inversions with at most n log ( I / n ) + O ( n ) element comparisons.

We show that verifying a given prefix code for optimality requires /spl Omega/(nlogn) time, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting.

Summary form only given. Consider the scenario in which a start-up communication company charges its network users by the cost of the minimum spanning tree (MST) they use in their protocols. Wanting to increase their profits, they aim at maximizing the cost of the MST of their network. We consider two different cases. In the first case, the company has a set of links with fixed cost vector W and wants to configure the network so that the MST of the network has the maximum possible cost. In the second case, the network topology is fixed, but the costs on the links assume d different values W/sub 1/, W/sub 2/, ..., W/sub d/ over the day. The company wants to fix the link costs to a value W~ = /spl Sigma//sub i/ p/sub i/ w/sub i/, for some weights p/sub 1/, p/sub 2/, ..., p/sub d/ where 0 /spl les/ p/sub i/ /spl les/ 1 and /spl Sigma//sub i/p/sub i/ = 1, so that the resulting network has a maximum-cost MST.