Abstract 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 $$1.3863\log n-1+o(1)$$ , 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 $$O(\log \log n)$$ bits of metadata per node, w.h.p., as compared to the $$\Theta (\log n)$$ bits per node required by treaps. In addition, we 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 zip-zip trees , which have an explicit bias based on key weights, so the expected depth of a key, k , with weight, $$w_k$$ , is $$O(\log (W/w_k))$$ , where W is the weight of all keys in the weighted zip-zip tree. Finally, we show that one can easily make zip-zip trees partially persistent with only O ( n ) space overhead w.h.p.

We present a randomized Õ(n^{3.5})-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes α_B(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^{3.5}) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^{3.5})-time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.

We consider the problem of sorting n items, given the outcomes of m pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in O(m + log T ) time and does O(log T ) comparisons, where T is the number of total orders consistent with the pre-existing comparisons.

We present the strict Fibonacci heap , the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. Strict Fibonacci heaps support make-heap, insert, find-min, meld and decrease-key in worst-case \(O(1)\) time, and delete and delete-min in worst-case \(O(\lg n)\) time, where \(n\) is the size of the heap. The data structure uses linear space. A previous solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld, and to use the pigeonhole principle in place of the redundant counter mechanism to maintain balance.

Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [ 8 ], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\mathrm{O}(\log\log n)\) time, where \(n\) is the number of heap items. 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 in the following amortized time bounds: \(\mathrm{O}(\log n)\) for delete-min and delete, \(\mathrm{O}(\log\log n)\) for decrease-key, and \(\mathrm{O}(1)\) for all other heap operations, including insert and meld, where \(n\) is the number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. 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 \(\mathrm{O}(\log\log n\cdot\log\log\log n)\) , where again items that are never deleted do not count in \(n\) . 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 Özkan [ 13 ].

This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. We give the first application of this notion to any sequential algorithm. We design a new heap data structure with a working-set property guaranteeing that the heap takes advantage of locality in heap operations. Our heap matches the optimal (worst-case) bounds of Fibonacci heaps but also provides the beyond-worst-case guarantee that the cost of extracting the minimum element is merely logarithmic in the number of elements inserted after it instead of logarithmic in the number of all elements in the heap. This makes the extraction of recently added elements cheaper. We prove that our working-set property guarantees universal optimality for the problem of ordering vertices by their distance from the source vertex: The sequence of heap operations generated by any run of Dijkstra's algorithm on a fixed graph possesses enough locality that one can couple the number of comparisons performed by any heap with our working-set bound to the minimum number of comparisons required to solve the distance ordering problem on this graph for a worst-case choice of arc lengths.

Abstract. 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 [Formula: see text] using only [Formula: see text] space, with [Formula: see text] amortized time, or even [Formula: see text] worst-case time, per operation. Sitarski, and (apparently independently) Brodnik, Carlsson, Demaine, Munro, and Sedgewick describe much better solutions that maintain a resizable array of size [Formula: see text] using only [Formula: see text] space, still with [Formula: see text] 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 shrinking the array. For every integer [Formula: see text], we show that [Formula: see text] space is sufficient for storing and accessing an array of size [Formula: see text], if [Formula: see text] space can be used briefly during grow and shrink operations. Accessing an item by index takes [Formula: see text] worst-case time, while grow and shrink operations take [Formula: see text] amortized time. Using an exact analysis of a growth game, we show that for any data structure from a wide class of data structures that uses only [Formula: see text] space to store the array, the amortized cost of grow is [Formula: see text], even if only grow and access operations are allowed. The time for grow and shrink operations cannot be made worst-case unless [Formula: see text].

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.

The smooth heap and the closely related slim heap are recently invented self-adjusting implementations of the heap (priority queue) data structure. They are simple to describe and efficient in practice. For both slim and smooth heaps, we derive the following tight bounds on the amortized time per operation: O(log n) for delete-min and delete; O(log log n) for decrease-key; and O(1) for make-heap, find-min, insert, and meld, where n is the current number of items in the heap. These bounds are tight not only for slim and smooth heaps, but for any heap in Iacono and Özkan's pure heap model, intended to capture all “self-adjusting” heap implementations. Slim and smooth heaps are the first known data structures to match Iacono and Özkan's lower bounds while satisying the constraints of their model.

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ(n1/k) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O(n1/k + logk n) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O(kn1/k) and a lower bound of Ω(n1/k + logk n) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ(n logk n) queue operations, for every k ≥ 2, an amortized number of Θ(logk n) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω(n1/k) queue operations per stack operation in the worst case.

The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be instance-optimal [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in sorting mode (n insertions followed by n delete-min operations), smooth heaps sort n numbers in O(nlg n) time. In this paper we describe a simpler variant of the smooth heap we call the slim heap. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.

Abstract We develop and analyze concurrent algorithms for the disjoint set union (“union-find” ) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchronization primitive. We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of $$O\biggl ( m \cdot \left( \log {\left( \frac{np}{m} + 1 \right) } + \alpha {\left( n, \frac{m}{np} \right) } \right) \biggr )$$ O ( m · log np m + 1 + α n , m np ) for a problem with n elements and m operations solved by p processes, where $$\alpha $$ α is a functional inverse of Ackermann’s function. We give two randomized algorithms that use only CAS and have the same work bound in expectation. The analysis of the second randomized algorithm is valid even if the scheduler is adversarial. Our DCAS and randomized algorithms take $$O(\log n)$$ O ( log n ) steps per operation, worst-case for the DCAS algorithm, high-probability for the randomized algorithms. Our work and step bounds grow only logarithmically with p, making our algorithms truly scalable. We prove that for a class of symmetric algorithms that includes ours, no better step or work bound is possible. Our work is theoretical, but Alistarh et al (In search of the fastest concurrent union-find algorithm, 2019), Dhulipala et al (A framework for static and incremental parallel graph connectivity algorithms, 2020) and Hong et al (Exploring the design space of static and incremental graph connectivity algorithms on gpus, 2020) have implemented some of our algorithms on CPUs and GPUs and experimented with them. On many realistic data sets, our algorithms run as fast or faster than all others.

We introduce the zip tree , 1 a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps [8], except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths ( unzipping and zipping ) rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion by Stephenson [10], Martínez and Roura [5], and Sprugnoli [9]. From a theoretical standpoint, this work provides two main results. First, zip trees require only O (log log n ) bits (with high probability) to represent the largest rank in an n -node binary search tree; previous data structures require O (log n ) bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists [7], and simplify Dean and Jones’ mapping between skip lists

We present an O(log d + log logm/n n)-time randomized PRAM algorithm for computing the connected components of an n-vertex, m-edge undirected graph with maximum component diameter d. The algorithm runs on an ARBITRARY CRCW (concurrent-read, concurrent-write with arbitrary write resolution) PRAM using O(m) processors. The time bound holds with good probability.

We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (α(n, m/(np)) + log(np/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.

Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985 [27], along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. We offer the first systematic proposal for settling the dynamic optimality conjecture. At the heart of our methods is what we term a simulation embedding: a mapping from executions to lists of keys that induces a target algorithm to simulate the execution. We build a simulation embedding for Splay by inducing it to perform arbitrary subtree transformations, and use this to show that if the cost of splaying a sequence of items is an upper bound on the cost of splaying every subsequence thereof, then Splay is dynamically optimal. We call this the subsequence property. Building on this machinery, we show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests. As a corollary, the subsequence property is also a necessary condition for dynamic optimality. The subsequence property also implies both the traversal [27] and deque [30] conjectures. The notions of simulation embeddings and bounding additive overheads should be of general interest in competitive analysis. For readers especially interested in dynamic optimality, we provide an outline of a proof that a lower bound on search costs by Wilber [32] has the subsequence property, and extensive suggestions for adapting this proof to Splay.

We introduce the hollow heap , a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete - min take O (1) time, worst case as well as amortized; delete and delete - min take O (log n ) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease - key operations and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

Disjoint set union is a basic problem in data structures with a wide variety of applications. We extend a known efficient sequential algorithm for this problem to obtain a simple and efficient concurrent wait-free algorithm running on an asynchronous parallel random access machine (APRAM). Crucial to our result is the use of randomization. Under a certain independence assumption, for a problem instance in which there are n elements, m operations, and l processes, our algorithm does θ(m (α{n, m/nl) + log (nl/m + 1 ))) expected work, where the expectation is over the random choices made by the algorithm and α is a functional inverse of Ackermann's function. In addition, each operation takes O(log n) steps with high probability.

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, the other to dense graphs. The former takes O (min { m 1/2 , n 2/3 } m ) time to insert m arcs into an n -vertex graph; the latter takes O ( n 2 log n ) time. Our sparse algorithm is substantially simpler than a previous O ( m 3/2 )-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O ( n 5/2 ) for dense graphs. Our algorithms rely for their efficiency on vertex numberings weakly consistent with topological order: we allow ties. Bounds on the size of the numbers give bounds on running time.

How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a particular input satisfies the desired input--output relation by running a checker on the input--output pair. Then one only needs to prove the correctness of the checker. For some problems, however, even such a checker may be too complicated to formally verify. There is a third alternative: augment the original program to produce not only an output but also a correctness certificate , with the property that a very simple program (whose correctness is easy to prove) can use the certificate to verify that the input--output pair satisfies the desired input--output relation. We consider the following important instance of this general question: How does one verify that the dominator tree of a flow graph is correct? Existing fast algorithms for finding dominators are complicated, and even verifying the correctness of a dominator tree in the absence of additional information seems complicated. We define a correctness certificate for a dominator tree, show how to use it to easily verify the correctness of the tree, and show how to augment fast dominator-finding algorithms so that they produce a correctness certificate. We also relate the dominator certificate problem to the problem of finding divergent spanning trees in a flow graph, and we develop algorithms to find such trees. All our algorithms run in linear time. Previous algorithms apply just to the special case of only trivial dominators, and they take at least quadratic time.

note Share on Addendum to "Dominator Tree Certification and Divergent Spanning Trees" Authors: Loukas Georgiadis University of Ioannina, Ioannina, Greece University of Ioannina, Ioannina, GreeceView Profile , Robert E. Tarjan Princeton University and Intertrust Technologies, Sunnyvale, CA Princeton University and Intertrust Technologies, Sunnyvale, CAView Profile Authors Info & Claims ACM Transactions on AlgorithmsVolume 12Issue 4September 2016 Article No.: 56pp 1–3https://doi.org/10.1145/2928271Published:16 August 2016Publication History 1citation145DownloadsMetricsTotal Citations1Total Downloads145Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree--based database systems do not do it. We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet worst-case access time remains logarithmic in the number of insertions. For any application of balanced trees in which the number of updates is polynomial in the tree size, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many, if not all, classic balanced tree structures. Our structure needs lg lg m + 1 bits of balance information per node, where m is the number of insertions and lg is the base-two logarithm, or lg lg n + O(1) with periodic rebuilding, where n is the number of nodes. An insertion takes up to two rotations and O(1) amortized time, not counting the time to find the insertion position. This is the same as in standard AVL trees. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node. Our techniques apply to other types of balanced trees, notably B-trees, as we show in a companion article, and particularly red-black trees, which can be viewed as a special case of B-trees.

We consider the minimum cost flow problem on graphs with unit capacities and its special cases. In previous studies, special purpose algorithms exploiting the fact that capacities are one have been developed. In contrast, for maximum flow with unit capacities, the best bounds are proven for slight modifications of classical blocking flow and push-relabel algorithms. In this paper we show that the classical cost scaling algorithms of Goldberg and Tarjan (for general integer capacities) applied to a problem with unit capacities achieve or improve the best known bounds. For weighted bipartite matching we establish a bound of O(\sqrt{rm}\log C) on a slight variation of this algorithm. Here r is the size of the smaller side of the bipartite graph, m is the number of edges, and C is the largest absolute value of an arc-cost. This simplifies a result of [Duan et al. 2011] and improves the bound, answering an open question of [Tarjan and Ramshaw 2012]. For graphs with unit vertex capacities we establish a novel O(\sqrt{n}m\log(nC)) bound. We also give the first cycle canceling algorithm for minimum cost flow with unit capacities. The algorithm naturally generalizes the single source shortest path algorithm of [Goldberg 1995].

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of ranks and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree) , whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.

The theory community has proposed several new heap variants in the recent past which have remained largely untested experimentally. We take the field back to the drawing board, with straightforward implementations of both classic and novel structures using only standard, well-known optimizations. We study the behavior of each structure on a variety of inputs, including artificial workloads, workloads generated by running algorithms on real map data, and workloads from a discrete event simulator used in recent systems networking research. We provide observations about which characteristics are most correlated to performance. For example, we find that the L1 cache miss rate appears to be strongly correlated with wallclock time. We also provide observations about how the input sequence affects the relative performance of the different heap variants. For example, we show (both theoretically and in practice) that certain random insertion-deletion sequences are degenerate and can lead to misleading results. Overall, our findings suggest that while the conventional wisdom holds in some cases, it is sorely mistaken in others.

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D⌋ – (M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to . Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no (n2−∊) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than . Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊)-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c-approximation for the diameter, i.e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n∊-approximation; no better results are known. We show that for any ∊ > 0, getting an additive n∊-approximation algorithm for the diameter running in (n2−δ) time for any δ > 2∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c-approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i.e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊(v) for the eccentricity ∊(v) such that max {R, · ∊(v)} ≤ ∊(v) ≤ min {D, · ∊(v)} where R = minv ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊′(v) with · ∊(v) ≤ ∊′(v) ≤ ∊(v).

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

Some database systems that use a form of B-tree for the underlying data structure do not do rebalancing on deletion. This means that a bad sequence of deletions can create a very unbalanced tree. Yet such databases perform well in practice. Avoidance of rebalancing on deletion has been justified empirically and by average-case analysis, but to our knowledge, no worst-case analysis has been done. We do such an analysis. We show that the tree height remains logarithmic in the number of insertions, independent of the number of deletions. Furthermore, the amortized time for an insertion or deletion, excluding the search time, is O (1), and nodes are modified by insertions and deletions with a frequency that is exponentially small in their height. The latter results do not hold for standard B-trees. By adding periodic rebuilding of the tree, we obtain a data structure that is theoretically superior to standard B-trees in many ways. Our results suggest that rebalancing on deletion not only is unnecessary but may be harmful.

In 1998, Chazelle [J. ACM, 47 (2000), pp. 1012--1027] introduced a new kind of meldable heap (priority queue) called the soft heap. Soft heaps trade accuracy for speed: the heap operations are allowed to increase the keys of certain items, thereby making these items bad, as long as the number of bad items in the data structure is at most $\varepsilon m$, where $m$ is the total number of insertions performed so far, and $\varepsilon$ is an error parameter. The amortized time per heap operation is $O(\lg \frac{1}{\varepsilon})$, reduced from $O(\lg n)$, where $n$ is the number of items in the heap. Chazelle used soft heaps in several applications, including a faster deterministic minimum-spanning-tree algorithm and a new deterministic linear-time selection algorithm. We give a simplified implementation of soft heaps that uses less space and avoids Chazelle's dismantling operations. We also give a simpler, improved analysis that yields an amortized time bound of $O(\lg \frac{1}{\varepsilon})$ for each deletion, $O(1)$ for each other operation.

Call a bipartite graph G = (X, Y ; E) balanced when |X| = |Y |. Given a balanced bipartite graph G with edge costs, the assignment problem asks for a perfect matching in G of minimum total cost. The Hungarian Method can solve assignment problems in time O(mn+n2log n), where n := |X| = |Y | and m := |E|. If the edge weights are integers bounded in magnitude by C >; 1, then algorithms using weight scaling, such as that of Gabow and Tarjan, can lower the time to O(m√n log(nC)). There are important applications in which G is unbalanced, with |X| ≠ |Y |, and we require a min-cost matching of size r := min(|X|, |Y |) or, more generally, of some specified size s ≤ r. The Hungarian Method extends easily to find such a matching in time O(ms + s2log r), but weightscaling algorithms do not extend so easily. We introduce new machinery to find such a matching in time O(m√s log(sC)) via weight scaling. Our results provide some insight into the design space of efficient weight-scaling matching algorithms.

We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space.

Let S be a set of n intervals in $\mathbb{R}$, and let $(\mathbf{S}, +)$ be any commutative semigroup. We assign a weight $\omega(s) \in \mathbf{S}$ to each interval in S. For a point $x \in \mathbb{R}$, let $S(x) \subseteq S$ be the set of intervals that contain x. Given a point $q \in \mathbb{R}$, the stabbing-semigroup query asks for computing $\sum_{s \in S(q)} \omega(s)$. We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case $O(\log n)$ time and supports both insertions and deletions of intervals in amortized $O(\log n)$ time. It is the first data structure that attains the optimal $O(\log n)$ bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in $O(\log_B n)$ I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees.

We present two online algorithms for maintaining a topological order of a directed n -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O( m 3/2 ) time. For sparse graphs ( m / n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O( n 5/2 ) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω( n 2 2 √2 lg n ) time by relating its performance to a generalization of the k -levels problem of combinatorial geometry. A completely different algorithm running in Θ( n 2 log n ) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

We introduce the rank-pairing heap, an implementation of heaps that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other heap implementations that match the bounds of Fibonacci heaps do so by maintaining a balance condition on the trees representing the heap. In contrast to these structures but like pairing heaps, our trees can evolve to have arbitrary (unbalanced) structure. Also like pairing heaps, our structure requires at most one cut and no other restructuring per key decrease, in the worst case: the only changes that can cascade during a key decrease are changes in node ranks. Although our data structure is simple, its analysis is not.

Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O (log 2 n ) amortized time on an n -node forest and each standard dynamic tree operation takes O (log n ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O (log n ) time per operation, including merging. This is best possible in a model of computation with an Ω( n log n ) lower bound for sorting n numbers, since such sorting can be done in O ( n ) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.

We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many database systems do not do it. We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet access time remains logarithmic in the number of insertions. For many applications of balanced trees, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many if not all classic balanced tree structures. Our structure needs O(log log m) bits of balance information per node, where m is the number of insertions, or O(log log n) with periodic rebuilding, where n is the number of nodes. An insertion takes up to two rotations and O(1) amortized time. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node.

We study algorithms for the minimum mean cycle problem, a parametric version of shortest path feasibility (SPF). The three basic approaches to the problem are cycle-based, binary search, and tree-based. The first two use an SPF algorithm as a subroutine, while the latter uses a parametric approach. When implementing the SPF-based methods, one has a choice of SPF algorithms and incremental optimization strategies. There are also several ways to handle precision issues. This leads to dozens of variants, which we systematically compare. Our experimental setup is more comprehensive than in previous studies. In our experiments, the tree-based method and two implementations of the cycle-based method outperformed other approaches, including binary search.

This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area.

We describe several new bottom-up approaches to problems in role engineering for Role-Based Access Control (RBAC). The salient problems are all NP-complete, even to approximate, yet we find that in instances that arise in practice these problems can be solved in minutes. We first consider role minimization, the process of finding a smallest collection of roles that can be used to implement a pre-existing user-to-permission relation. We introduce fast graph reductions that allow recovery of the solution from the solution to a problem on a smaller input graph. For our test cases, these reductions either solve the problem, or reduce the problem enough that we find the optimum solution with a (worst-case) exponential method. We introduce lower bounds that are sharp for seven of nine test cases and are within 3.4% on the other two. We introduce and test a new polynomial-time approximation that on average yields 2% more roles than the optimum. We next consider the related problem of minimizing the number of connections between roles and users or permissions, and we develop effective heuristic methods for this problem as well. Finally, we propose methods for several related problems.

We present linear-time algorithms for the classic problem of finding dominators in a flowgraph, and for several other problems whose solutions require evaluating a function defined on paths in a tree. Although all these problems had linear-time solutions previously, our algorithms are simpler, in some cases substantially. Our improvements come from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favor certain nodes; replacement of random-access table look-up by a radix sort; and a more careful partitioning of a tree into easily managed parts. In addition to finding dominators, our algorithms find nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis of a flowgraph, and build the component tree of a weighted tree. Our algorithms do not require the power of a random-access machine; they run in linear time on a pointer machine. The genesis of our work was the discovery of a subtle error in the analysis of a previous allegedly linear-time algorithm for finding dominators. That algorithm was an attempt to simplify a more complicated algorithm, which itself was intended to correct errors in a yet earlier algorithm. Our work provides a systematic study of the subtleties in the dominators problem, the techniques needed to solve it in linear time, and the range of application of the resulting methods. We have tried to make our techniques as simple and as general as possible and to understand exactly how earlier approaches to the dominators problem were either incorrect or overly complicated.

The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Høyer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps ) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in Høyer's analysis.

We show that any priority queue data structure that supports insert , delete , and find-min operations in pq ( n ) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. More specifically, the new data structure supports insert , meld and find-min operations in O (1) amortized time, and delete operations in O ( pq ( n ) + α( n )) amortized time, where α( n ) is a functional inverse of the Ackermann function, and where n this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. We also show that when all keys are integers in the range [1, N ], we can replace n in the bound stated previously by min{ n , N }.Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with O (log log n ) amortized time per operation, or O (√log log n ) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic O ( m log log n )-time algorithm and a randomized O ( m √log log n )-time algorithm. For sparse enough graphs, these bounds improve on the O ( m + n log n ) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.

No abstract available.

We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible.Our solution decomposes DSSP into an offline job selection phase followed by an online task dispatching phase. We model the former as a knapsack problem and explore several solutions to it, describe a new dispatching algorithm for the latter, and compare both with existing methods. Our theoretical results show that while DSSP is NP-hard and inapproximable in general, our two-phase scheduling method guarantees a good performance bound for many special cases. Our empirical results include an evaluation of scheduling algorithms on a real animation-rendering workload; we present a characterization of this workload in a companion paper. The workload records eight weeks of activity on a 1,000-CPU cluster used to render portions of the full-length animated feature film Shrek 2 in 2004. We show that our improved scheduling algorithms can substantially increase the aggregate value of completed jobs compared to existing practices. Our new task dispatching algorithm LCPF performs well by several metrics, including job completion times as well as the aggregate value of completed jobs.

We present efficient data structures to maintain dynamic set of rectangles, each with priority assigned to it, such that we can efficiently find the rectangle of maximum priority containing a query point. Our data structures support insertions and deletions of rectangles. In one dimension, when rectangles are intervals, our most efficient data structure supports queries and insertions in O(log n) time, deletions in O(log n loglog n) time and requires linear space. When intervals are guaranteed to be nonoverlapping (but one can be nested within the other) we obtain a simpler data structure that supports all operations in O(log n) time.

In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min, insert, delete, decrease-key, and meld. In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min, decrease-key, or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting).To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find. In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if χ ε A. We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well.We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive---each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log^4 n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of...

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\Delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\Delta$, there exists an initial distribution of tokens with imbalance $\Delta$ for which the time to reduce the imbalance to even $\Delta/2$ is at least $\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

We study the parameterized complexity of three NP-hard graph completion problems. The minimum fill-in problem asks if a graph can be triangulated by adding at most k edges. We develop O(ck m) and O(k2mn+f(k)) algorithms for this problem on a graph with n vertices and m edges. Here f(k) is exponential in k and the constants hidden by the big-O notation are small and do not depend on k. In particular, this implies that the problem is fixed-parameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biology, asks if a graph can be made proper interval by adding no more than k edges. We show that the problem is FPT by providing a simple search-tree-based algorithm that solves it in O(ck m)-time. Similarly, we show that the parameterized version of the strongly chordal graph completion problem is FPT by giving an O(ck m log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions within the same time bounds.

No abstract available.

We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2 log n off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms. 1 Introduction We describe the first work-optimal minimum spanning forest (MSF) algorithm that runs in O(log n) time. The algorithm uses a random-sampling technique previously used by Karger, Klein, and Tarjan in a sequential linear-time algorithm and by Cole, Klein, and Tarjan in a parallel algorithm. These previous algorithms have the following form. Choose a random subset of edges, and recursively calculate the MSF of the sample graph, the graph consisting of the chosen edges. Use the recursively calculated minimum spanning forest to identify edges ...

tice, especially for applications that require worst-case time bounds or persistence.

. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \\Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \\Delta, there exists an initial distribution of tokens with imbalance \\Delta for which the time to reduce the imbalance to even \\Delta=2 is at least \\Omega\\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl...

Article Persistent lists with catenation via recursive slow-down Share on Authors: Haim Kaplan Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile , Robert E. Tarjan Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 93–102https://doi.org/10.1145/225058.225090Online:29 May 1995Publication History 31citation523DownloadsMetricsTotal Citations31Total Downloads523Last 12 Months13Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.

A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively findmax) operation, which returns the element of least (greatest) key, but it does not allow a general deletemin (deletemax) operation. Such a data structure is also called a mindeque (maxdeque). Whereas implementing heap-ordered deques in constant time per operation is a solved problem, catenating heap-ordered deques in sublogarithmic time has remained open until now. This paper provides an efficient implementation of catenable heap-ordered deques, yielding constant amortized time per operation. The important algorithmic technique employed is an idea that we call data-structural bootstrapping; we abstract heap-ordered deques by representing them by their minimum elements, thereby reducing catenation to simple insertion, The efficiency of the resulting data structure depends upon the complexity of a special case of path compression that we prove takes linear time.

Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe general algorithms for this problem and prove their correctness under fairly weak assumptions about P. We establish that the worst-case running time of these algorithms is $\Theta(m + n \log n)$ for 2-edge-connectivity and biconnectivity where n and m denote the number of vertices and edges, respectively, in the input graph. By refining the basic algorithms we obtain the first linear time algorithms for computing a minimal 2-edge-connected spanning subgraph and for computing a minimal biconnected spanning subgraph. We also devise general algorithms for computing a minimal spanning subgraph in directed graphs. These algorithms allow us to simplify an earlier algorithm of Gibbons, Karp, Ramachandran, Soroker, and Tarjan for computing a minimal strongly connected spanning subgraph. We also provide the first tight analysis of the latter algorithm, showing that its worst-case time complexity is $\Theta(m + n \log n)$.

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect.>

We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons. 1 Introduction We consider the problem of finding a minimum spanning tree in a connected graph with real-valued edge weights. This problem has a long and rich history; the first fully realized algorithm was devised by Boruvka in the 1920's [3]. An informative survey paper by Graham and Hell [9] describes the history of the problem up to 1985. In the last two decades faster and faster algorithms were found, the fastest being an algorithm of Gabow, Galil, and Spencer [7] (see also [8]), with a running time of O(m log fi(m; n)) on a ...

This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log log k ) time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

In this paper, network flow algorithms for bipartite networks are studied. A network $G = (V,E)$ is called bipartite if its vertex set V can be partitioned into two subsets $V_1 $ and $V_2 $ such that all edges have one endpoint in $V_1 $ and the other in $V_2 $. Let $n = |V|$, $n_1 = |V_1 |$ , $n_2 = |V_2 |$, $m = |E|$ and assume without loss of generality that $n_1 \leqslant n_2 $. A bipartite network is called unbalanced if $n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow algorithms can be substantially sped up when applied to unbalanced networks. The basic idea in these improvements is a two-edge push rule that allows one to “charge” most computation to vertices in $V_1 $, and hence develop algorithms whose running times depend on $n_1 $ rather than n. For example, it is shown that the two-edge push version of Goldberg and Tarjan’s FIFO preflow-push algorithm runs in $O(n_1 m + n_1^3 )$ time and that the analogous version of Ahuja and Orlin’s excess scaling algorithm runs in $O(n_1 m + n_1^2 \log U)$ time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.

This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem. Unique representations are applied to obtain efficient data structures for maintaining a dynamic collection of sets/sequences under queries that test the equality of a pair of objects. The data structure for set equality testing tests equality of sets in constant time and processes set updates in $O(\log m)$ amortized time and $O(\log m)$ space, where m denotes the total number of updates performed. It is based on an efficient implementation of cascades of CONS operations on uniquely stored S-expressions. The data structure for sequence equality testing tests equality of sequences in constant time and processes updates in $O(\sqrt {n\log m} = \log m)$ amortized time and $O(\sqrt n )$ amortized space where n denotes the length of the sequence that is updated and m denotes the total number of updates performed.

Based on a new version of the Hopcroft and Tarjan planarity testing algorithm, this paper develops an $O(m\log n)$-time algorithm to find a maximal planar subgraph.

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure.>

Komlós has devised a way to use a linear number of binary comparisons to test whether a given spanning tree of a graph with edge costs is a minimum spanning tree. The total computational work required by his method is much larger than linear, however. This paper describes a linear-time algorithm for verifying a minimum spanning tree. This algorithm combines the result of Komlós with a preprocessing and table look-up method for small subproblems and with a previously known almost-linear-time algorithm. Additionally, an optimal deterministic algorithm and a linear-time randomized algorithm for sensitivity analysis of minimum spanning trees are presented.

A derivation in a transformational system such as a graph grammar may be redundant in the sense that the exact order of the transformations may not affect the final outcome; all that matters is that each transformation, when applied, is applied to the correct substructure. By taking advantage of this redundancy, we can develop an efficient encoding scheme for such derivations. This encoding scheme has a number of diverse applications. It can be used in efficient enumeration of combinatorial objects or for compact representation of program and data structure transformations. It can also be used to derive lower bounds on lengths of derivations. It is shown, for example, that $\Omega ( n \log n )$ applications of the associative and commutative laws are required in the worst case to transform an n-variable expression over a binary associative, commutative operation into some other equivalent expression. Similarly, it is shown that $\Omega ( n\log n )$ “diagonal flips” are required in the worst case to transform one n-vertex numbered triangulated planar graph into some other one. Both of these lower bounds have matching upper bounds. An $O( n\log n )$ upper bound for associative, commutative operations was known previously, whereas here an $O( n\log n )$ upper bound for diagonal flips is obtained.

Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general-purpose pattern-matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase's bottom-up algorithm for pattern preprocessing. A preliminary implementation of our algorithm runs ten times faster than Chase's (1987) implementation on the hardest problem instances. Our preprocessing algorithm has the advantage of being on-line with respect to pattern additions and deletions. It also adapts to favorable input instances, and on Hoffmann and O'Donnell's (1982) class of simple patterns, it performs better than their special-purpose algorithm tailored to this class. We show how to modify our algorithm using a new decomposition method to obtain a space/time tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern-matching algorithm that handles a wide subclass of Hoffmann and O'Donnell's (1982) simple patterns.

We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm requiring optimal O(A + n log n) expected work and optimal O(logn) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(logn log log n log n) expected time a , and a simpler algorithm requiring O(n log n) expected work. The serial algorithm corresponding to the latter is among the simplest known algorithms requiring O(n log n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A + n log n + K log n) expected work and O(logn log log n log n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps. Keywords: randomized, parallel, trapez...

An algorithmfor minimum-cost matching on a general graph with integral edge costs is

Abstract We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider. An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).

We give a new Ο(n log log n)-time deterministic linear-time algorithm for triangulating simple n-vertex polygons, which avoids the use of complicated data-structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run in Ο(n log* n) time. The major new techniques employed are the efficient location of horizontal visibility edges which partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. This latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.

Given an ordered universe U, we study the problem of representing each subset of U by a unique binary search tree so that dictionary operations can be performed efficiently.While efficient randomized solutions to the problem are known, its deterministic complexity has remained unexplored.We exhibit representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense.Our results demonstrate an exponential separation between the deterministic and randomized complexities of the problem.We apply unique representations to obtain efficient data structures for maintaining a collection of sets/sequences under queries that test the equality of a pair of objects.Our data structure for set equality-testing is based on an efficient implementation of cascades of CONS operations on uniquely stored Sexpressions.

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].

A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in Ο( nm (log n )min{log( nC ), m log n }) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C . This bound is comparable to those of the fastest previously known algorithms.

Recently, Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in $O(n^3 )$ time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of $O(nm\log (n^2 /m)$ on m-arc networks. Ahuja and Orlin developed a variant of Goldberg’s algorithm that uses scaling and runs in $O(nm + (n^2 \log U)$ time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of $O(nm + n^2 \log U/\log \log U)$ is obtained by using a nonconstant scaling factor. Second, an even better bound of $O(nm + n^2 (\log U)^{1/2} )$ is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to $O(nm\log (({n / m})(\log U)^{{1 / 2}} + 2))$. This result shows that the combined use of three different techniques, results in speed not obtained by using any of the techniques alone. The above bounds are all for a unit-cost random access machine. Also considered is a semilogarithmic computation model in which the bounds increase by an additive term of $O(m\log _n U)$, which is the time needed to read the input in the model.

This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimum-cost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in $O(\sqrt {nm} \log (nN))$ time, where $n,m$, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum.

The classical maximum flow problem sometimes occurs in settings in which the arc capacities are not fixed but are functions of a single parameter, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. In this paper it is shown that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst-case time bound. Faster algorithms for a variety of combinatorial optimization problems follow from the result.

Mannila and Ukkonen [Lecture Notes in Computer Science 225, Springer-Verlag, New York, 1986, pp. 236–243] have studied a variant of the classical disjoint set union (equivalence) problem in which an extra operation, called de-union, can undo the most recently performed union operation not yet undone. They proposed a way to modify standard set union algorithms to handle de-union operations. In this paper several algorithms are analyzed based on their approach. The most efficient such algorithms have an amortized running time of $O({{\log n} / {\log \log n}})$ per operation, where n is the total number of elements in all the sets. These algorithms use $O(n\log n)$ space, but the space usage can be reduced to $O(n)$ by a simple change. The authors prove that any separable pointer-based algorithm for the problem requires $\Omega ({{\log n} / {\log \log n}})$ time per operation, thus showing that our upper bound on amortized time is tight.

We present an algorithm that triangulates a simple polygon on n vertices in Ο(n log* n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/).>

We present algorithms for matching and related problems that run on an EREW PRAM with p processors. Given is a bipartite graph G with n vertices, m edges, and integral edge costs at most N in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in O(√nm log (nN)(log(2p))/p) time and O(m) space, for p ≤ m/(√nlog2n). For p = 1 this improves the best known sequential algorithm, and is within a factor of log (nN) of the best known bound for the problem without costs (maximum cardinality matching). For p > 1 the time is within a factor of log p of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.

A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in O(nm(log n) min{log(nC), mlog n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms.

All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an O ( n 3 ) time bound on an n -vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O ( nm log( n 2 / m )) time on an n -vertex, m -edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in O ( n 2 log n ) time using n processors and O ( m ) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses n processors but requires O ( n 2 ) space.

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into $n - 2$ triangles by adding $n - 3$ nonintersecting diagonals. We propose an $O(n\log \log n)$-time algorithm for this problem, improving on the previously best bound of $O(n\log n)$ and showing that triangulation is not as hard as sorting. Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.

In "A linear-time algorithm for triangulating a simple polygon" [Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), 380-388. 486], the analysis showing that the authors' triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far they have been unable to obtain a linear-time algorithm for the triangulation problem. They have been able to obtain an O(n loglogn)-time algorithm, however. The details are described in "An O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon," SIAM Journal on Computing 17, 1 (February, 1988), to appear.

We introduce a framework for solving minimum-cost flow problems. Our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. We show how to extend techniques developed for the maximum flow problem to improve the quality of a solution. This framework allows us to achieve Ο(min(n3, n5/3 m2/3, nm log n) log (nC)) running time.

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps ), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n -item heap in O (log n ) amortized time and all other standard heap operations in O (1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case bounds, where n is the number of vertices and m the number of edges in the problem graph: O ( n log n + m ) for the single-source shortest path problem with nonnegative edge lengths, improved from O ( m log ( m/n +2) n ); O ( n 2 log n + nm ) for the all-pairs shortest path problem, improved from O ( nm log ( m/n +2) n ); O ( n 2 log n + nm ) for the assignment problem (weighted bipartite matching), improved from O ( nm log ( m/n +2) n ); O ( mβ ( m, n )) for the minimum spanning tree problem, improved from O ( m log log ( m/n +2) n ); where β ( m, n ) = min { i | log ( i ) n ≤ m/n }. Note that β ( m, n ) ≤ log * n if m ≥ n . Of these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities.

We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the subpolygon of P consisting of points that are visible from a segment within P; (iii) Preprocessing P so that for any query ray r emerging from some fixed edge e of P, we can find in logarithmic time the first intersection of r with the boundary of P; (iv) Preprocessing P so that for any query point x in P, we can find in logarithmic time the portion of the edge e that is visible from x; (v) Preprocessing P so that for any query point x inside P and direction u, we can find in logarithmic time the first point on the boundary of P hit by the ray at direction u from x; (vi) Calculating a hierarchical decomposition of P into smaller polygons by recursive polygon cutting, as in [Ch]. (vii) Calculating the (clockwise and counterclockwise) “convex ropes” (in the terminology of [PS]) from a fixed vertex s of P lying on its convex hull, to all other vertices of P. All these algorithms are based on a recent linear time algorithm of Tarjan and Van Wyk for triangulating a simple polygon, but use additional techniques to make all subsequent phases of these algorithms also linear.

This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and effiient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.

Article Free Access Share on A new approach to the maximum flow problem Authors: A V Goldberg Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , R E Tarjan Computer Science Department, Princeton University, Princeton, NJ and AT&T Bell Laboratories, Murray Hill, NJ Computer Science Department, Princeton University, Princeton, NJ and AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 136–146https://doi.org/10.1145/12130.12144Published:01 November 1986Publication History 200citation2,891DownloadsMetricsTotal Citations200Total Downloads2,891Last 12 Months101Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Computer Science Department

A simple polygon with n vertices is triangulated by adding to it n-3 line segments between its vertices that partition the interior of the polygon into triangles.We present an algorithm for triangulating a simple polygon in time proportional to its size.This result has a number of applications in computational geometry.

In this paper we explore two themes in data structure design: amortized computational complexity and self adjustment. We are motivated by the following observations. In most applications of data structures, we wish to perform not just a single operation but a sequence of operations, possibly having correlated behavior. By averaging the running time per operation over a worst-case sequence of operations, we can sometimes obtain an overall time bound much smaller than the worst-case time per operation multiplied by the number of operations. We call this kind of averaging amortization. Standard kinds of data structures, such as the many varieties of balanced trees, are specifically designed so that the worst-case time per operation is small. Such efficiency is achieved by imposing an explicit structural constraint that must be maintained during updates, at a cost of both running time and storage space. However, if amortized running time is the complexity measure of interest, we can guarantee efficiency without maintaining a structural constraint. Instead, during each access or update operation we adjust the data structure in a simple, uniform way. We call such a data structure self adjusting. In this paper we develop the skew heap, a self-adjusting form of heap related to the leftist heaps of Crane and Knuth. (What we mean by a heap has also been called a “priority queue” or a “mergeable heap”.) Skew heaps use less space than leftist heaps and similar worst-case-efficient data structures and are competitive in running time, both in theory and in practice, with worst-case structures. They are also easier to implement. We derive an information-theoretic lower bound showing that skew heaps have minimum possible amortized running time, to within a constant factor, on any sequence of certain heap operations.

For a Jordan curve C in the plane, let x_{1},x_{2},...,x_{n} be the abscissas of the intersection points of C with the x-axis, listed in the order the points occur on C. We call x_{1},x_{2},...,x_{n} a Jordan sequence. In this paper we describe an O(n)-time algorithm for recognizing and sorting Jordan sequences. The problem of sorting such sequences arises in computational geometry and computational geography. Our algorithm is based on a reduction of the recognition and sorting problem to a list-splitting problem. To solve the list-splitting problem we use level linked search trees.

The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an n -node splay tree, all the standard search tree operations have an amortized time bound of O (log n ) per operation, where by “amortized time” is meant the time per operation averaged over a worst-case sequence of operations. Thus splay trees are as efficient as balanced trees when total running time is the measure of interest. In addition, for sufficiently long access sequences, splay trees are as efficient, to within a constant factor, as static optimum search trees. The efficiency of splay trees comes not from an explicit structural constraint, as with balanced trees, but from applying a simple restructuring heuristic, called splaying , whenever the tree is accessed. Extensions of splaying give simplified forms of two other data structures: lexicographic or multidimensional search trees and link/cut trees.

Abstract We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear‐time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chvátal and Thomassen, we then prove that, if a mixed multigraph of radius r has any strongly connected orientation, it must have an orientation of radius at most 42 + Ar. The proof gives a polynomial‐time algorithm for constructing such an orientation.

We consider the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. We describe two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. We present and analyze efficient update algorithms for biased search trees. We list several applications of such trees.

In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in $O(n + m)$ time and space on a graph of n vertices and m edges. A parallel implementation runs in $O(\log n)$ time and $O(n + m)$ space using $O(n + m)$ processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in $O(n^2 /p)$ time and $O(n^2 )$ space using any number $p \leqq n^2 /\log ^2 n$ of processors, on a concurrent-read, exclusive-write parallel RAM. The last algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique that simplifies and improves computation of various functions on trees is introduced. This technique typically requires $O(\log n)$ time using processors and $O(n)$ space on an exclusive-read exclusive-write parallel RAM.

Previous article Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic HypergraphsRobert E. Tarjan and Mihalis YannakakisRobert E. Tarjan and Mihalis Yannakakishttps://doi.org/10.1137/0214020PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs." SIAM Journal on Computing, 14(1), pp. 254–255 Previous article FiguresRelatedReferencesCited ByDetails Learning Hyperedge Replacement Grammars for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 41, No. 3 | 1 Mar 2019 Cross Ref Paired threshold graphsDiscrete Applied Mathematics, Vol. 250 | 1 Dec 2018 Cross Ref Detecting Highly Overlapping Community Structure by Model-based Maximal Clique Expansion2018 IEEE International Conference on Big Data (Big Data) | 1 Dec 2018 Cross Ref Strict chordal and strict split digraphsDiscrete Applied Mathematics, Vol. 216 | 1 Jan 2017 Cross Ref Growing Graphs from Hyperedge Replacement Graph GrammarsProceedings of the 25th ACM International on Conference on Information and Knowledge Management | 24 October 2016 Cross Ref Tree decompositions and social graphsInternet Mathematics, Vol. 12, No. 5 | 16 May 2016 Cross Ref Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland SubgraphsNathan Lindzey and Ross M. McConnellSIAM Journal on Discrete Mathematics, Vol. 30, No. 1 | 12 January 2016AbstractPDF (857 KB)A faster algorithm to recognize even-hole-free graphsJournal of Combinatorial Theory, Series B, Vol. 113 | 1 Jul 2015 Cross Ref Edge deletion problems: Branching facilitated by modular decompositionTheoretical Computer Science, Vol. 573 | 1 Mar 2015 Cross Ref A new augmentation based algorithm for extracting maximal chordal subgraphsJournal of Parallel and Distributed Computing, Vol. 76 | 1 Feb 2015 Cross Ref A New Class of Lineage Expressions over Probabilistic Databases Computable in P-TimeScalable Uncertainty Management | 1 Jan 2013 Cross Ref On Finding Tucker Submatrices and Lekkerkerker-Boland SubgraphsGraph-Theoretic Concepts in Computer Science | 1 Jan 2013 Cross Ref BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSESDiscrete Mathematics, Algorithms and Applications, Vol. 04, No. 01 | 13 April 2012 Cross Ref On $3$-Colorable $P_5$-Free GraphsFrédéric Maffray and Grégory MorelSIAM Journal on Discrete Mathematics, Vol. 26, No. 4 | 27 November 2012AbstractPDF (1151 KB)Certifying algorithmsComputer Science Review, Vol. 5, No. 2 | 1 May 2011 Cross Ref A Novel Branching Strategy for Parameterized Graph Modification ProblemsCombinatorial Optimization and Applications | 1 Jan 2010 Cross Ref Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphsDiscrete Applied Mathematics, Vol. 157, No. 15 | 1 Aug 2009 Cross Ref Polarity of chordal graphsDiscrete Applied Mathematics, Vol. 156, No. 13 | 1 Jul 2008 Cross Ref A Fixed-Parameter Tractable Approach for the Wavelength Assignment Problem in Transparent NetworksIEEE Communications Letters, Vol. 12, No. 7 | 1 Jul 2008 Cross Ref Two fixed-parameter algorithms for Vertex Covering by Paths on TreesInformation Processing Letters, Vol. 106, No. 2 | 1 Apr 2008 Cross Ref Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic EncodingsLogic for Programming, Artificial Intelligence, and Reasoning | 1 Jan 2008 Cross Ref A Fixed-Parameter Tractable Algorithm for the Wavelength Assignment in WDM Mesh Networks2008 IEEE International Conference on Communications | 1 Jan 2008 Cross Ref Advances in Register Allocation TechniquesThe Compiler Design Handbook | 7 December 2009 Cross Ref Certifying Algorithms for Recognizing Interval Graphs and Permutation GraphsDieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, and Jeremy P. SpinradSIAM Journal on Computing, Vol. 36, No. 2 | 17 February 2012AbstractPDF (253 KB)Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc GraphsGraph-Theoretic Concepts in Computer Science | 1 Jan 2006 Cross Ref On Split-Coloring ProblemsJournal of Combinatorial Optimization, Vol. 10, No. 3 | 1 Nov 2005 Cross Ref Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval BigraphsPavol Hell and Jing HuangSIAM Journal on Discrete Mathematics, Vol. 18, No. 3 | 1 August 2006AbstractPDF (199 KB)Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval GraphsHaim Kaplan, Ron Shamir, and Robert E. TarjanSIAM Journal on Computing, Vol. 28, No. 5 | 28 July 2006AbstractPDF (361 KB)Minimal elimination ordering inside a given chordal graphGraph-Theoretic Concepts in Computer Science | 17 June 2005 Cross Ref Fixed-parameter tractability of graph modification problems for hereditary propertiesInformation Processing Letters, Vol. 58, No. 4 | 1 May 1996 Cross Ref Parallel computation of perfect elimination schemes using partition techniques on triangulated graphsComputers & Mathematics with Applications, Vol. 29, No. 6 | 1 Mar 1995 Cross Ref An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graphTheoretical Computer Science, Vol. 134, No. 2 | 1 Nov 1994 Cross Ref An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph30th Annual Symposium on Foundations of Computer Science | 1 Jan 1989 Cross Ref Doubly Lexical Orderings of MatricesAnna LubiwSIAM Journal on Computing, Vol. 16, No. 5 | 31 July 2006AbstractPDF (3081 KB)Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mappingProceedings 35th Annual Symposium on Foundations of Computer Science Cross Ref Volume 14, Issue 1| 1985SIAM Journal on Computing1-255 History Submitted:29 May 1984Published online:13 July 2006 InformationCopyright © 1985 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0214020Article page range:pp. 254-255ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

We propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in 0[n+m] time and space on a graph of n vertices and m edges. A parallel implmentation runs in 0[log n] time and 0[n+m] space using 0[n+m] processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in 0[n/sup 2/p] time and 0[n/sup 2/] space using any number p ⩽ n/sup 2/log/sup 2/-n of processors, on a concurrent-read, exclusive-write parallel RAM. The latter algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique which simplifies and improve computation of various functions on tress is introduced. This technique typically requires 0(log n) time using 0(n) space on an exclusive-read exclusive-write parallel RAM.

Three techniques in computational geometry are explored: Scaling solves a problem by viewing it at increasing levels of numerical precision; activation is a restricted type of update operation, useful in sweep algorithms; the Cartesian tree is a data structure for problems involving maximums and minimums. These techniques solve the minimum spanning tree problem in Rk1 and Rk@@@@ in O(n(lg n)rlg lg n) time and O(n) space, where for Rk@@@@ and k ≥ 3, r = k-2; for Rk1, r = 1, 2, 4 for k = 3, 4, 5 and r = k for k > 5. Other problems solved include Rk1and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zkp all nearest neighbors (1 ≤ p ≤ @@@@).

Article Amortized efficiency of list update rules Share on Authors: Daniel Dominic Sleator View Profile , Robert Endre Tarjan View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 488–492https://doi.org/10.1145/800057.808718Published:01 December 1984 15citation466DownloadsMetricsTotal Citations15Total Downloads466Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union.We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.

Abstract Let G be a directed graph containing n vertices, one of which is a distinguished source s, and m edges, each with a non‐negative cost. We consider the problem of finding, for each possible sink vertex v, a pair of edge‐disjoint paths from s to v of minimum total edge cost. Suurballe has given an O(n2 logn)‐time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O(m log(1+ m/n)n) time and O(m) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O(1) per edge on the paths.

We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We show that any pointer machine that solves this problem requires $\Omega (\log \log n)$ time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, we present an algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\log n)$ on the number of bits per word) that requires $O(1)$ time per query and $O(n)$ preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, we obtain an almost-linear-time (and linear-space) algorithm.

Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. Rose, Tarjan and Lueker [SIAM J. Comput., 5 (1976), pp. 266–283] have given a linear-time algorithm to test whether a graph is chordal, which Yannakakis has modified to test whether a hypergraph is acyclic. Here we develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which we call maximum cardinality search A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acyclic relational data bases.

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in 0(m+n) time and 0(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(ma(m+n, n)+n) time and 0(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining a fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings on nonbipartite graphs.

We use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. Unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. Instead, whenever the tree is accessed, certain adjustments take place. (In the case of heaps, the adjustment is a sequence of exchanges of children, in the case of search trees the adjustment is a sequence of rotations.) Self-adjusting trees are efficient in an amortized sense: any particular operation may be slow but any sequence of operations must be fast.

Several space-efficmnt implementations of the two most common and useful kinds of graph search, namely, breadth-first search and depth-first search, are discussed.A straightforward implementation of each method requires n bits and n + O(1) pointers of auxiliary storage, where n is the number of vertices in the graph.We devise methods that need only 2n + m bits, of which m are read-only, where rn is the number of edges in the graph.We save space by folding the queue or stack required by the search into the graph representation; two of our methods for depth-first search are variants of the Deutsch-Schorr-Waite list-marking algorithm.Our algorithms are expressed in a version of Dijkstra's guarded command language.

Asymptotically Ught tune-space trade-offs for pebblmg three d~fferent classes of directed aeychc graphs are derived Let N be the size of the graph, S the number of avadable pebbles, and T the time necessary for pebbling the graph A time-space trade-off of the form ST = O(N 2) ls proved for pebbhng (usmg only black pebbles) a specml class of permutaaon graphs that tmplement the bR-reversal permutation.If we are allowed to use black and whtte pebbles~ the time-space trade-off is shown to be of the form (:) r=o T¢ +0(~.A tune-space trade-off of the form /N\OIN/S~ T= SOI~ ) ~s proved for pebbling a class of graphs constructed by stacking superconcentrators m series.This tunespace trade-off holds whether we use only black or black and white pebbles A tune-space trade-off of the form T --$2 2°~N/s) Is proved for the class of all directed acychc graphs This trade-off also holds whether we use only black or black and white pebbles Categories and Subject Descriptors: F 1.3 [Computation by Abstract Devices]: Complexity Classes-relatwns among complexay measures, F.2 3 [Analysis of Algorithms and Problem Complexity] Trade-offs Among Complextty Measures; G.2.

This paper describes an algorithm to construct, for each expression in a given program text, a symbolic expression whose value is equal to the value of the text expression for all executions of the program. We call such a mapping from text expressions to symbolic expressions a cover. Covers are useful in such program optimization techniques as constant propagation and code motion. The particular cover constructed by our methods is in general weaker than the covers obtainable by the methods of [Ki], [FKU], [RL], [R2] but our method has the advantage of being very efficient. It requires $O(m\alpha (m,n) + l)$ operations if extended bit vector operations have unit cost, where n is the number of vertices in the control flow graph of the program, m is the number of edges, l is the length of the program text, and $\alpha $ is related to a functional inverse of Ackermann’s function [T2]. Our method does not require that the program be well-structured nor that the flow graph be reducible.

We present a linear-time algorithm to recognize the class of vertex series-parallel (VSP) digraphs. Our method is based on the relationship between VSP digraphs and the class of edge series-parallel multidigraphs. As a byproduct of our analysis, we obtain efficient methods to compute the transitive closure and transitive reduction of VSP digraphs, and to test isomorphism of minimal VSP digraphs.

A data structure is proposed to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Each operation requires O(log n) time. Using this data structure, new fast algorithms are obtained for the following problems: (1) Computing nearest common ancestors. (2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows. (3) Computing certain kinds of constrained minimum spanning trees. (4) Implementing the network simplex algorithm for minimum-cost flows. The most significant application is (2); an O(mn log n)-time algorithm is obtained to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.

A general method is described for solving path problems on directed graphs.Such path problems include finding shortest paths, solving sparse systems of hnear equaUons, and carrying out global flow analysis of computer programs The method consists of two steps First, a collecUon of regular expressions representmg sets of paths m the graph Is constructed This can be done by using any standard algorithm, such as Gaussmn or Gauss-Jordan elimination.Next, a natural mapping from regular expressions into the gwen problem domain is applied.The mappmgs required to find shortest paths are exhibited, sparse systems of hnear equations are solved, and global flow analysis Is carned out.The results provide a general-purpose algonthm for solwng any path problem and show that the problem of constructing path expressions is in some sense the most general path problem.

Let G = (V, E) be a directed graph with a distinguished source vertex s.The single-source path expression problem is to find, for each vertex v, a regular expression P (s, v) which represents the set of all paths in G from s to v A solution to this problem can be used to solve shortest path problems, solve sparse systems of linear equations, and carry out global flow analysis.A method is described for computing path expressions by dwidmg G mto components, computing path expressions on the components by Gaussian elimination, and combining the solutions This method requires O(ma(m, n)) time on a reducible flow graph, where n Is the number of vertices m G, m is the number of edges in G, and a is a functional inverse of Ackermann's function The method makes use of an algonthm for evaluating functions defined on paths in trees.A smapllfied version of the algorithm, which runs in O(m log n) time on reducible flow graphs, is quite easy to implement and efficient m practice KEY WORDS AND PHRASES: Ackermann's function, code optimizaUon, compdmg, dominators, Gaussian ehmmaUon, global flow analysis, graph algorithm, linear algebra, path compression, path expression, path problem, path sequence, reducible flow graph, regular expressmn, shortest path, sparse matrix CR CATEGORIES 4 12, 4.34, 5 14, 5.22, 5.25, 5 32 paths from s to v in G.By reinterpreting the U,., and * operations used to construct regular expressions, we can use a solution to the single-source path expression problem to solve other kinds of path problems, including those mentioned above [30].We thus obtain a general-purpose algorithm for solving any path problem on a given graph.This paper describes a decomposition method for computing path expressions.The method divides the graph G into components based upon the dominator tree of G, computes a path expression for each component by Gaussian elimination, and combines the solutions using an algorithm for evaluating functions defined on trees [9, 29].The algorithm requires O(mct(m, n)) time plus time to compute path expressions within the components, where n is the number of vertices in G, m is the Permission to copy without fee all or part of this matenal is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the pubhcatlon and its date appear, and notice is given that copying is by permlssmn of the Association for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission

The basic problem considered is that of scheduling n unit-time tasks, with arbitrary release times and deadlines, so as to minimize the maximum task completion time. Previous work has shown that this problem can be solved rather easily when all release times are integers. We are concerned with the general case in which noninteger release times are allowed, a generalization that considerably increases the difficulty of the problem even for only a single processor. Our results are for the one-processor case, where we provide an $O(n\log n)$ algorithm based on the concept of “forbidden regions”.

Finding a minimum weighted complete matching on a set of vertices in which the distances satisfy the triangle inequality is of general interest and of particular importance when drawing graphs on a mechanical plotter. The “greedy” heuristic of repeatedly matching the two closest unmatched points can be implemented in worst-case time $O(n^2 \log n)$, a reasonable savings compared to the general minimum weighted matching algorithm which requires time proportional to $n^3 $ to find the minimum cost matching in a weighted graph. We show that, for an even number n of vertices whose distances satisfy the triangle inequality, the ratio of the cost of the matching produced by this greedy heuristic to the cost of the minimal matching is at most ${}_3^4 n^{\lg _2^3 } - 1$, $\lg _2^3 \approx 0.58496$, and there are examples that achieve this bound. We conclude that this greedy heuristic, although desirable because of its simplicity, would be a poor choice for this problem.

We describe a new data structure for maintaining collections of weighted items. The access time for an item of weight w in a collection of total weight W is proportional to log(W/w) in the worst case (which is optimal in a certain sense), and several other useful operations can be made to work just, as fast. The data structure is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.

A parsing method based on the triconnected decomposition of a biconnected graph is presented. The parsing algorithm runs in linear time and handles a large class of flow graphs. The applications of this algorithm to flow analysis and to the automatic structuring of programs are discussed.

Researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (Exceptions include the work of Angluin and Valiant [1], Karp [7], and Schnorr [9].) In this paper we analyze the expected running time of four algorithms for solving graph connectivity problems. Our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs.

Let G be a directed graph such that for each vertex v in G, the successors of v are ordered Let C be any equivalence relation on the vertices of G.The congruence closure C* of C is the finest equivalence relation containing C and such that any two vertices having corresponding successors equivalent under C* are themselves equivalent under C* Efficient algorithms are described for computing congruence closures in the general case and in the following two special cases.0) G under C* is acyclic, and (it) G is acychc and C identifies a single pair of vertices.The use of these algorithms to test expression eqmvalence (a problem central to program verification) and to test losslessness of joins in relational databases is described KEY WORDS AND PHRASES common subexpresslon, congruence closure, decision procedure, expression equivalence, graph algorithm, lossless join, relational database, theory of equality, unification, uniform word problem CR CATEGORIES 4 12, 4.33, 4 34, 5.24, 5 25, 5 32

In this paper we explore the use of 2-3 trees to represent sorted lists. We analyze the worst-case cost of sequences of insertions and deletions in 2-3 trees under each of the following three assumptions: (i) only insertions are performed; (ii) only deletions are performed; (iii) deletions occur only at the small end of the list and insertions occur only away from the small end. Our analysis leads to a data structure for representing sorted lists when the access pattern exhibits a (perhaps time-varying) locality of reference. This structure has many of the properties of the representation proposed by Guibas, McCreight, Plass and Roberts [A new representation for linear lists, Proc. Ninth Annual Symposium on Theory of Computing, Boulder, CO, 1977, pp. 49–60], but it is substantially simpler and may be practical for lists of moderate size.

We analyze several “level-oriented” algorithms for packing rectangles into a unit-width, infinite-height bin so as to minimize the total height of the packing. For the three algorithms we discuss, we show that the ratio of the height obtained by the algorithm to the optimal height is asymptotically bounded, respectively, by 2, 1.7, and 1.5. The latter two improve substantially over the performance bounds for previously proposed algorithms. In addition, we give more refined bounds for special cases in which the widths of the given rectangles are restricted and in which only squares are to be packed.

In this paper we study a pebbling problem that models the storage requirements of various kinds of computation. Sethi has shown this problem to be $NP$-hard and Lingas has shown a generalization to be P-space complete. We prove the original problem P-space complete by using a modification of Lingas’s proof. The pebbling problem is an example of a P-space complete problem not exhibiting any obvious quantifier alternation.

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only $O(\sqrt n )$ vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

Given a matroid, where each element has a realvalued cost and is colored red or green; we seek a minimum cost base with exactly q red elements. This is a simple case of the matroid intersection problem. A general algorithm is presented. Its efficiency is illustrated in the special case of finding a minimum spanning tree with q red edges; the time is O(m log log n + n α (n,n) log n). Efficient algorithms are also given for job scheduling matroids and partition matroids. An algorithm is given for finding a minimum spanning tree where a vertex r has prespecified degree; it shows this problem is equivalent to finding a minimum spanning tree, without the degree constraint. An algorithm is given for finding a minimum spanning tree on a directed graph, where the given root r has prespecified degree; the time is O(m log n), the same as for the problem without the degree constraint.

We examine a pebbling problem which has been used to study the storage requirements of various models of computation. Sethi has shown this problem to be NP-hard and Lingas has shown a generalization to be P-space complete. We prove the original problem P-space complete by employing a modification of Lingas's proof. The pebbling problem is one of the few examples of a P-space complete problem not exhibiting any obvious quantifier alternation.

This paper derives asymptotically tight bounds on the time-space tradeoffs for pebbling three different classes of directed acyclic graphs. Let N be the size of the graph, S the number of available pebbles, and T the time necessary for pebbling the graph. (a) A time space tradeoff of the form ST = t(N2) is proved for a special class of permutation graphs which implement the bit reversal permutation. (b) A time-space tradeoff of the form T = S t(N/S)t(N/S) is proved for a class of graphs constructed by stacking superconcentrators in series. (c) A time-space tradeoff of the form T = S.22t(N/S)is proved for pebbling general directed acyclic graphs.

We present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any General Series Parallel digraph. Our analysis is based on the relationship between General Series Parallel digraphs and a class of well known models of electrical networks.

An algonthm that merges sorted hsts represented as height-balanced binary trees 1s given If the hsts have lengths m and n (m _< n) then the merging procedure runs m O(m log(n/m)) steps, which is the same order as the lower bound on all companson-based algorithms for this problem

Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons.The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations.The algorithms have O((m + n)a(m + n, n)) running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's function By usmg one or more of these algorithms m combination with other techniques, it is possible to solve the followmg graph problems m O(ma(m, n)) tnne, where m Is the number of edges and n Is the number of vertices m the problem graph A Venfymg a minimum spanning tree m an undirected graph (Best previously known time bound O(m log log n).) B Flndmg dominators in a flow graph (Best previously known tune bound O(n log n + m).) C Solvmg a path problem on a reducible flow graph.(Best previously known time bound.O(m log n) ) Application A is discussed KEY WORDS AND PHRASES balanced tree, dominators, equivalence relation, global flow analysis, graph algonthm, mmnnum spanning tree, path compression, path problem, tree CR CAT~60~mS: 4.12, 4.34, 5.25, 5.32 LINK(v, w)" Combme the trees with roots v and w into a single tree by addmg an edge (v, w) (this makes v the parent of w).UPDATE(r, x)" lfr ts the root of a tree and r has label l, replace I by x ® IWe present algorithms for carrying out on-line an arbitrary sequence of m EVAL, LINK, and UPDATE instructions on a forest initially consisting of n one-vertex trees.Our first and simplest algorithm uses path compression to solve the EVAL-LINK-UPDATE

A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in O ( m log n ) time, where m is the number of edges and n is the number of vertices in the problem graph. A more sophisticated implementation runs in O ( m α( m , n )) time, where α( m , n ) is a functional inverse of Ackermann's function. Both versions of the algorithm were implemented in Algol W, a Stanford University version of Algol, and tested on an IBM 370/168. The programs were compared with an implementation by Purdom and Moore of a straightforward O ( mn )-time algorithm, and with a bit vector algorithm described by Aho and Ullman. The fast algorithm beat the straightforward algorithm and the bit vector algorithm on all but the smallest graphs tested.

This paper describes a data structure which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. The structure has many of the properties of the representation proposed by Guibas, McCreight, Plass, and Roberts [4], but is substantially simpler and may be practical for lists of moderate size. The analysis of our structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper shows that any such machine requires non-linear time in the worst case to compute unions of disjoint sets on-line. All set union algorithms known to the author are instances of the model and are thus subject to the derived bound. One of the known algorithms achieves the bound to within a constant factor.

Abstract Chu and Liu, Edmonds, and Bock have independently devised an efficient algorithm to find an optimum branching in a directed graph. We give an implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges. A modification for dense graphs gives a running time of 0(n2). We also show that the unmodified algorithm runs in 0(n(log n)2 +m) time on an average graph, assuming a uniform probability distribution.

We present an algorithm which finds a maximum independent set in an n-vertex graph in $O(2^{n/3})$ time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph with n vertices and maximum in-degree d , there is a pebbling strategy which requires at most c(d) n/log n pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.

This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem solvable in polynomial space is solvable in polynomial time. This result suggests that the theory of combinational games is difficult.

This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with $O(m\log \log n)$ worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense graphs (those for which m is $\Omega (n^{1 + \varepsilon } )$ for some positive constant $\varepsilon $); 3. an $O(n)$ worst-case algorithm for planar graphs; 4. relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.

This paper considers problems in which the object is to add a minimum-weight set of edges to a graph so as to satisfy a given connectivity condition. Simple characterizations of the minimum number of edges necessary to make a directed graph strongly connected and to make an undirected graph bridge-connected or biconnected are given. Efficient algorithms for finding such minimum sets of edges are discussed. It is shown that the weighted versions of these problems are NP-complete.

We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.

We develop linear-time algorithms to find maximum weighted and unweighted degree-constrained subgraphs (b-matchings) of a tree. We use a generalization of an algorithm for finding a maximum 2-matching in a tree.

We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. We give a new linear-time algorithm to calculate the fill-in produced by any elimination ordering, and we give two new related algorithms for finding orderings with special properties. One algorithm, based on breadth-first search, finds a perfect elimination ordering, if any exists, in $O(n + e)$ time, if the problem graph has n vertices and e edges. An extension of this algorithm finds a minimal (but not necessarily minimum) ordering in $O(ne)$ time. We conjecture that the problem of finding a minimum ordering is NP-complete

We consider a generalization, which we call the Shannon switching game on vertices, of a familiar board game called HEX. We show that determining who wins such a game if each player plays perfectly is very hard; in fact, it is as hard as carrying out any polynomial-space-bounded computation. This result suggests that the theory of combinatorial games is difficult.

A graph-theoretic elimination process is considered which is related to performing Gaussian elimination on sparse symmetric and unsymmetric systems of linear equations. The authors discuss good algorithms for finding elimination orderings, showing that a generalization of breadth-first search, called lexicographic search, can be used to find perfect orderings in O(n+e) time and minimal orderings in O(ne) time, if the problem graph is undirected and has n vertices and e edges. Also given are efficient (though slower) algorithms for generating such orderings on directed graphs. It is claimed that the minimum ordering problem for directed graphs is NP-complete, and it is conjectured that it is also NP-complete for undirected graphs. The authors include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.

TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C.A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m > n FINDs and n --1 intermixed UNIONs, then kima(m, n) _~ t(m, n) < k:ma(m, n) for some positive constants ki and k2, where a(m, n) is related to a functional inverse of Ackermann's functmn and as very slow-growing. KEY WORDS AND PHRASES. algorithm, complexity,

ABSTRACT Backtrack algorithms for listing certain kinds of subgraphs of a graph are described and analyzed. Included are algorithms for listing all spanning trees, all cycles, all simple cycles, or all of certain other kinds of paths. The algorithms have 0(V+E) space requirements and 0(V+E+EN) time requirements, if the problem graph has V vertices, E edges, and N subgraphs of the type to be listed.

An algorithm of Dinic for finding the maximum flow in a network is described. It is then shown that if the vertex capacities are all equal to one, the algorithm requires at most $O(|V|^{1/2} \cdot |E|)$ time, and if the edge capacities are all equal to one, the algorithm requires at most $O(|V|^{2/3} \cdot |E|)$ time. Also, these bounds are tight for Dinic’s algorithm. These results are used to test the vertex connectivity of a graph in $O(|V|^{1/2} \cdot |E|^2 )$ time and the edge connectivity in $O(|V|^{5/3} \cdot |E|)$ time.

An algorithm proposed by Dinic for finding maximum flows in networks and by Hopcroft and Karp for finding maximum bipartite matchings is applied to graph connectivity problems. It is shown that the algorithm requires 0(V1/2E) time to find a maximum set of node-disjoint paths in a graph, and 0(V2/3E) time to find a maximum set of edge disjoint paths. These bounds are tight. Thus the node connectivity of a graph may be tested in 0(V5/2E) time, and the edge connectivity of a graph may be tested in 0(V5/3E) time.

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has O ( V ) time and space bounds, where V is the number of vertices in G . An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds.

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of $O(V\log V + E)$ if V is the number of vertices and E is the number of edges in the graph. This bound compares favorably with the $O(V(V + E))$ time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the $O(V + E\log E)$ time bound of a known algorithm for finding dominators in reducible graphs. If $E \geqq V\log V$, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.

Many problems in program optimization have been solved by applying a technique called interval analysis to the flow graph of the program. A flow graph which is susceptible to this type of analysis is called reducible. This paper describes an algorithm for testing whether a flow graph is reducible. The algorithm uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. When the algorithm is implemented on a random access computer, it requires O(E log* E) time to analyze a graph with E edges, where log* x = min{i/logix≤1}. The time bound compares favorably with the O(E log E) bound of a previously known algorithm.

An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V + E)$ time and space to analyze a graph with V vertices and E edges. The algorithm is both theoretically optimal to within a constant factor and efficient in practice.

An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm is based on a backtracking procedure of Tiernan, but uses a lookahead and labeling technique to avoid unnecessary work. It has a time bound of $O((V \cdot E)(C + 1))$ when applied to a graph with V vertices, E edges, and C elementary circuits.

New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n:

AI~STRAC'r.The problem of sorting a sequence of numbers using a network of queues and stacks is presented.A characterization of sequences sortable using parallel queues is given, and partial characterizations of sequences sortable using parallel stacks and networks of queues are given.

The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected components of a directed graph and at algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by $k_1 V + k_2 E + k_3 $ for some constants $k_1 ,k_2 $, and $k_3 $, where V is the number of vertices and E is the number of edges of the graph being examined.