Arrow Research search

Author name cluster

Robert Endre Tarjan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

65 papers
2 author rows

Possible papers

65

FOCS Conference 2024 Conference Paper

Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps

  • Bernhard Haeupler
  • Richard Hladík
  • Václav Rozhon
  • Robert Endre Tarjan
  • Jakub Tetek

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.

Details

SODA Conference 2023 Conference Paper

A Nearly-Tight Analysis of Multipass Pairing Heaps

  • Corwin Sinnamon
  • Robert Endre Tarjan

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

Details

SODA Conference 2023 Conference Paper

A Tight Analysis of Slim Heaps and Smooth Heaps

  • Corwin Sinnamon
  • Robert Endre Tarjan

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.

Details

SODA Conference 2022 Conference Paper

Simulating a stack using queues

  • Haim Kaplan
  • Robert Endre Tarjan
  • Or Zamir
  • Uri Zwick

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 Θ( n 1/ 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 ( n 1/ k + log k n ) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O ( kn 1/ k ) and a lower bound of Ω( n 1/ k + log k 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 log k n ) queue operations, for every k ≥ 2, an amortized number of Θ(log k n ) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω( n 1/ k ) queue operations per stack operation in the worst case.

Details

SODA Conference 2019 Conference Paper

A New Path from Splay to Dynamic Optimality

  • Caleb C. Levy
  • Robert Endre Tarjan

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.

Details

SODA Conference 2014 Conference Paper

Better Approximation Algorithms for the Graph Diameter

  • Shiri Chechik
  • Daniel H. Larkin
  • Liam Roditty
  • Grant Schoenebeck
  • Robert Endre Tarjan
  • Virginia Vassilevska Williams

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 ( n 2− ∊ ) 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 ( n 2− δ ) 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 = min v ∊(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 ).

Details

SODA Conference 2014 Conference Paper

Disjoint Set Union with Randomized Linking

  • Ashish Goel
  • Sanjeev Khanna
  • Daniel H. Larkin
  • Robert Endre Tarjan

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.

Details

FOCS Conference 2012 Conference Paper

A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs

  • Lyle Ramshaw
  • Robert Endre Tarjan

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+n 2 log 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 + s 2 log 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.

Details

STOC Conference 2012 Conference Paper

Strict fibonacci heaps

  • Gerth Stølting Brodal
  • George Lagogiannis
  • Robert Endre Tarjan

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. A previous, very complicated, 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. We use the pigeonhole principle in place of the redundant counter mechanism.

Details

STOC Conference 2003 Conference Paper

Dynamic rectangular intersection with priorities

  • Haim Kaplan
  • Eyal Molad
  • Robert Endre Tarjan

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 log log 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.

Details

STOC Conference 2002 Conference Paper

Meldable heaps and boolean union-find

  • Haim Kaplan
  • Nira Shafrir
  • Robert Endre Tarjan

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.

Details

FOCS Conference 1994 Conference Paper

Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping

  • Haim Kaplan
  • Ron Shamir
  • Robert Endre Tarjan

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. >

Details

FOCS Conference 1992 Conference Paper

Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

  • Adam L. Buchsbaum
  • Rajamani Sundar
  • Robert Endre Tarjan

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. >

Details

FOCS Conference 1988 Conference Paper

Dynamic Perfect Hashing: Upper and Lower Bounds

  • Martin Dietzfelbinger
  • Anna R. Karlin
  • Kurt Mehlhorn
  • Friedhelm Meyer auf der Heide
  • Hans Rohnert
  • Robert Endre Tarjan

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/). >

Details

FOCS Conference 1987 Conference Paper

Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"

  • Robert Endre Tarjan
  • Christopher J. Van Wyk

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.

Details

FOCS Conference 1984 Conference Paper

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms

  • Michael L. Fredman
  • Robert Endre Tarjan

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.

Details

FOCS Conference 1984 Conference Paper

Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)

  • Robert Endre Tarjan
  • Uzi Vishkin

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.

Details

STOC Conference 1984 Conference Paper

Scaling and Related Techniques for Geometry Problems

  • Harold N. Gabow
  • Jon Louis Bentley
  • Robert Endre Tarjan

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 R k 1 and R k @@@@ in O( n ( lg n ) r lg lg n ) time and O( n ) space, where for R k @@@@ and k ≥ 3, r = k-2; for R k 1 , r = 1, 2, 4 for k = 3, 4, 5 and r = k for k > 5. Other problems solved include R k 1 and R k all nearest neighbors, post office and maximum spanning tree; R k maxima, R k rectangle searching problems, and Z k p all nearest neighbors (1 ≤ p ≤ @@@@).

Details

STOC Conference 1983 Conference Paper

A Linear-Time Algorithm for a Special Case of Disjoint Set Union

  • Harold N. Gabow
  • Robert Endre Tarjan

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( m α( m + n, n )+ n ) time and 0( n ) space, where α 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.

Details

STOC Conference 1981 Conference Paper

A Data Structure for Dynamic Trees

  • Daniel Dominic Sleator
  • Robert Endre Tarjan

We propose a data structure 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. Our data structure requires O(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems: (1) Computing deepest 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 the transshipment problem. Our most significant application is (2); we obtain an O(mn log n)-time algorithm 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.

Details

FOCS Conference 1980 Conference Paper

Biased 2-3 Trees

  • Samuel W. Bent
  • Daniel Dominic Sleator
  • Robert Endre Tarjan

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.

Details

FOCS Conference 1979 Conference Paper

Efficient Algorithms for Simple Matroid Intersection Problems

  • Harold N. Gabow
  • Robert Endre Tarjan

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.

Details

STOC Conference 1979 Conference Paper

The Pebbling Problem is Complete in Polynomial Space

  • John R. Gilbert
  • Thomas Lengauer
  • Robert Endre Tarjan

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.

Details

STOC Conference 1979 Conference Paper

The recognition of Series Parallel digraphs

  • Jacobo Valdes
  • Robert Endre Tarjan
  • Eugene L. Lawler

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.

Details

STOC Conference 1979 Conference Paper

Upper and Lower Bounds on Time-Space Tradeoffs

  • Thomas Lengauer
  • Robert Endre Tarjan

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.

Details

STOC Conference 1978 Conference Paper

A Representation for Linear Lists with Movable Fingers

  • Mark R. Brown
  • Robert Endre Tarjan

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.

Details

FOCS Conference 1977 Conference Paper

Application of a Planar Separator Theorem

  • Richard J. Lipton
  • Robert Endre Tarjan

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.

Details

STOC Conference 1977 Conference Paper

Reference Machines Require Non-linear Time to Maintain Disjoint Sets

  • Robert Endre Tarjan

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.

Details

TCS Journal 1976 Journal Article

Computing an st-numbering

  • Shimon Even
  • Robert Endre Tarjan

Lempel, Even and Cederbaum proved the following result: Given any edge {st} in a biconnected graph G with n vertices, the vertices of G can be numbered from 1 to n so that vertex s receives number 1, vertex t receives number n, and any vertex except s and t is adjacent both to a lower-numbered and to a higher-numbered vertex (we call such a numbering an st-numbering for G). They used this result in an efficient algorithm for planarity-testing. Here we provide a linear-time algorithm for computing an st-numbering for any biconnected graph. This algorithm can be combined with some new results by Booth and Lueker to provide a linear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.

Details DOI

STOC Conference 1976 Conference Paper

Space Bounds for a Game of Graphs

  • Wolfgang J. Paul
  • Robert Endre Tarjan
  • James R. Celoni

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.

Details

STOC Conference 1975 Conference Paper

Algorithmic Aspects of Vertex Elimination

  • Donald J. Rose
  • Robert Endre Tarjan

We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric and unsymmetric systems of linear equations. We 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 0(n+e) time and minimal orderings in 0(ne) time, if the problem graph is undirected and has n vertices and e edges. We also give efficient (though slower) algorithms for generating such orderings on directed graphs. We claim that the minimum ordering problem for directed graphs is NP-complete, and conjecture that it is also NP-complete for undirected graphs. We include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.

Details

STOC Conference 1974 Conference Paper

Testing Graph Connectivity

  • Robert Endre Tarjan

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(V 1/2 E) time to find a maximum set of node-disjoint paths in a graph, and 0(V 2/3 E) 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(V 5/2 E) time, and the edge connectivity of a graph may be tested in 0(V 5/3 E) time.

Details

STOC Conference 1973 Conference Paper

Testing Flow Graph Reducibility

  • Robert Endre Tarjan

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/log i x≤1}. The time bound compares favorably with the O(E log E) bound of a previously known algorithm.

Details

STOC Conference 1972 Conference Paper

Linear Time Bounds for Median Computations

  • Manuel Blum 0001
  • Robert Floyd 0001
  • Vaughan R. Pratt
  • Ronald L. Rivest
  • Robert Endre Tarjan

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: f(i,n) ≤ 103n/18 < 5.73n, for 1 ≤ i ≤ n. A lower bound is shown deductively to be: f(i,n) ≥ n+min(i,n−i+l) + [log 2 (n)] − 4, for 2 ≤ i ≤ n−1, or, for the case of computing medians: f([n/2],n) ≥ 3n/2 − 3

Details
v2026.09.13