Robert Tarjan

We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple algorithm with a running time of , where , , and are the number of items, the number of pre-existing comparisons, and the number of total orders consistent with the outcomes of the pre-existing comparisons, respectively. The algorithm does comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of on the number of comparisons has a time bound of and is significantly more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient insertion into a sorted list.

An electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different cost per unit of energy. Traversing a given road segment requires a specified amount of energy that may be positive, zero or negative. The car can only traverse a road segment if it has enough charge to do so (the charge cannot drop below zero), and it cannot charge its battery beyond its capacity. To travel from one point to another the car needs to choose a travel plan consisting of a path in the network and a recharging schedule that specifies how much energy to charge at each charging station on the path, making sure of having enough energy to reach the next charging station or the destination. The cost of the plan is the total charging cost along the chosen path. We reduce the problem of computing plans between every two junctions of the …

This disclosure relates to systems and methods for managing protected electronic content that employ relatively efficient messaging schemes. Rights management architectures are described that may, among other things, provide end-to-end protection of content keys from their point of origination at a content creator and/or content service to end user devices. Certain embodiments may further provide for message protocols where fewer messages are sent in connection with a protected content license request process, thereby reducing latency associated with license request and provisioning processes.

The pairing heap, introduced by Fredman et al. [3], is a self-adjusting heap data structure that is both simple and efficient. A variant introduced in the same paper is the multipass pairing heap. Standard pairing heaps do just two linking passes during delete-min, a pairing pass and an assembly pass. In contrast, multipass pairing heaps do repeated pairing passes, in which nodes are linked in adjacent pairs, until only a minimum-key node remains. We obtain the following amortized time bounds for operations on n-item multipass pairing heaps: O(log n) for delete-min and delete; O(log log n log log log n) for decrease-key; and O(1) for all other heap operations, including insert and meld. This is the first analysis giving an O(log n) bound for delete-min. Our analysis is tight for all operations except possibly decrease-key, for which Fredman [2] and separately Iacono and Ozkan [6] proved an Ω(log log n) lower bound.

We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan’s algorithm; (2) a cycle-finding algorithm; and (3) a bidirectional search algorithm.

A resizable array is an array that can grow and shrink by the addition or removal of items from its end, or both its ends, while still supporting constant-time access to each item stored in the array given its index. Since the size of an array, i.e., the number of items in it, varies over time, space-efficient maintenance of a resizable array requires dynamic memory management. A standard doubling technique allows the maintenance of an array of size N using only O(N) space, with O(1) amortized time, or even O(1) worst-case time, per operation. Sitarski and Brodnik et al. describe much better solutions that maintain a resizable array of size N using only N + O(√N) space, still with O(1) time per operation. Brodnik et al. give a simple proof that this is best possible. We distinguish between the space needed for storing a resizable array, and accessing its items, and the temporary space that may be needed while growing or …

We define simple variants of zip trees, called zip-zip trees, which provide several advantages over zip trees, including overcoming a bias that favors smaller keys over larger ones. We analyze zip-zip trees theoretically and empirically, showing, e.g., that the expected depth of a node in an n-node zip-zip tree is at most , which matches the expected depth of treaps and binary search trees built by uniformly random insertions. Unlike these other data structures, however, zip-zip trees achieve their bounds using only bits of metadata per node, w.h.p., as compared to the bits per node required by treaps. In fact, we even describe a “just-in-time” zip-zip tree variant, which needs just an expected O(1) number of bits of metadata per node. Moreover, we can define zip-zip trees to be strongly history independent, whereas treaps are generally only weakly history independent. We also introduce biased …

Since the invention of the pairing heap by Fredman et al., it has been an open question whether this or any other simple "self-adjusting" heap supports decrease-key operations on -item heaps in time. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations on an -item heap in the following amortized time bounds: for delete-min and delete, for decrease-key, and for all other heap operations, including insert and meld. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is . Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and Ozkan; for multipass pairing heaps our bounds are tight except for decrease-key, which by the lower bounds of Fredman and Iacono and \"Ozkan must take amortized time if delete-min takes time.