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.

Corrigendum to ACM Transactions on Programming Languages and Systems , 20(6):1265--1296, 1998.

We develop a telecommunications architecture based on IP routers and compare it empirically to the current TDM hierarchy. The study is based on two premises: first that data traffic will continue to grow much faster than voice traffic and will be mostly IP, and second, that IP routers and networks will soon achieve the scalability and dependability necessary to provide the service quality expected of telecommunications networks. The IP architecture exploits a number of mechanisms to improve network efficiency: mesh restoration requires less spare bandwidth than SONET rings; private line services are carried as virtual leased lines, enabling more fine-grained bandwidth offerings; a voice subnetwork uses OC-48 links rather than DS-1 trunk groups, so it requires less total bandwidth to achieve the same blocking probability; and the multiplying inefficiencies of layer-by-layer routing in the TDM hierarchy are avoided. We find that an all-IP architecture could offer much greater network efficiency and considerable capital savings. We examine how technology must evolve to support such an architecture.

We consider the problem of online robot navigation in an unfamiliar two-dimensional environment, using comparatively limited sensing information. In particular, the robot has local sensors to detect the proximity of obstacles and permit boundary-following, and it is able to determine its current distance and relative bearing to its final destination (via distance queries). By contrast, most previous algorithms for online navigation have assumed that the robot knows its exact current position. Because determining exact location is prone to error that accumulates over time, the usefulness of such algorithms may be limited. In contrast, distance queries give less information, but the accuracy of each query is independent of the number of queries, which means distance queries can be more robust. We formally define our model and give new, efficient navigation algorithms and lower bounds for this setting.

We study the problem of constructing the deterministic equivalent of a nondeterministic weighted finite-state automaton (WFA). Determinization of WFAs has important applications in automatic speech recognition (ASR). We provide the first polynomial-time algorithm to test for the twins property, which determines if a WFA admits a deterministic equivalent. We also give upper bounds on the size of the deterministic equivalent; the bound is tight in the case of acyclic WFAs. Previously, Mohri presented a superpolynomial-time algorithm to test for the twins property, and he also gave an algorithm to determinize WFAs. He showed that the latter runs in time linear in the size of the output when a deterministic equivalent exists; otherwise, it does not terminate. Our bounds imply an upper bound on the running time of this algorithm. Given that WFAs can expand exponentially in size when determinized, we explore why those that occur in ASR tend to shrink when determinized. According to ASR folklore, this phenomenon is attributable solely to the fact that ASR WFAs have simple topology, in particular, that they are acyclic and layered. We introduce a very simple class of WFAs with this structure, but we show that the expansion under determinization depends on the transition weights: some weightings cause them to shrink, while others, including random weightings, cause them to expand exponentially. We provide experimental evidence that ASR WFAs exhibit this weight dependence. That they shrink when determinized, therefore, is a result of favorable weightings in addition to special topology. These analyses and observations have been used to design a new, approximate WFA determinization algorithm, reported in a separate paper along with experimental results showing that it achieves significant WFA size reduction with negligible impact on ASR performance.

Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networks---trees and bus-based networks---are studied. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on On-Line Algorithms, AMS, 1991, pp. 11--64] and "factoring."

We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted finite-state automata (WFAs). Analogues of classical automata determinization and minimization algorithms then provide a general method to produce smaller but equivalent WFAs. We extend this approach by introducing the notion of approximate determinization. We provide an algorithm that, when applied to language models for the North American Business task, achieves 25-35% size reduction compared to previous techniques, with negligible effects on recognition time and accuracy.

We present two new data structure tools—disjoint set union with bottom-up linking, and pointer-based radix sort—and combine them with bottom-level microtrees to devise the first linear-time pointer-machine algorithms for off-line least common ancestors, minimum spanning tree (MST) verification, randomized MST construction, and computing dominators in a flowgraph.

We give algorithms and data structures that maintain the 2-edge and 2-vertex-connected components of a graph under insertions and deletions of edges and vertices, where deletions occur in a backtracking fashion (i.e., deletions undo the insertions in the reverse order). Our algorithms run in $\Theta (\log n)$ worst-case time per operation and use $\Theta (n)$ space, where n is the number of vertices. Using our data structure we can answer queries, which ask whether vertices u and v belong to the same 2-connected component, in $\Theta (\log n)$ worst-case time.

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.

Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given; these lead to optimum algorithm which runs in time Θ2n(n − 1)!m, where n is the length of the list and m is the number of requests. The previous best algorithm, an adaptation of a more general algorithm due to Manasse et al. (1988), runs in time Θ(n!)2m.

We discuss space-efficient encoding schemes for planar graphs and maps. Our results improve on the constants of previous schemes and can be achieved with simple encoding algorithms. They are near-optimal in number of bits per edge.

We obtain linear upper and lower bounds for the on-line generalized Steiner problem and on-line Steiner problem on a directed graph.

: We describe a fault-tolerant distributed storage system for local area networks. Our system implements Persistent, Associative, Shared Object (PASO) memory. A PASO memory stores a set of data objects that can be accessed by associative search queries from all nodes in an ensemble of machines. This approach to distributed memory has been used in a number of systems, and provides a convenient and useful model for parallel and distributed applications. PASO memory is amenable to adaptive implementations that relocate data objects in response to changing network configurations and access patterns, making it a good candidate for an efficient, fault-tolerant storage system. The paper defines the semantics of PASO memory, gives a basic design strategy, discusses memory primitives and their costs, and discusses adaptive techniques for improving efficiency. 1 Introduction This paper presents PASO, a Persistent, Associative, Shared Object memory, and studies algorithms that implement fault-t...

The page migration problem is to manage a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to that page by other processors incur a cost proportional to the network distance. At times the page may migrate between processors at cost proportional to the distance times D, a page size factor. The problem is to schedule movements on-line so that the total cost of memory references is within a constant factor c of the best off-line schedule. An algorithm that does so is called c-competitive. Black and Sleator gave 3-competitive deterministic on-line algorithms for uniform networks (complete graphs with unit edge lengths) and for trees with arbitrary edge lengths. No good deterministical gorithm is known for general networks with arbitrary edge lengths. Randomized algorithms are presented for the migration problem that are both simple and better than 3-competitive against an oblivious adversary. An algorithm for uniform graphs is given. It is approximately 2.28-competitive as D grows large. A second, more powerful algorithm that works on graphs with arbitrary edge distances is also given. This algorithm is approximately 2.62-competitive (or, 1 plus the golden ratio) for large D. Both these algorithms use random bits only during an initialization phase, and from then on run deterministically. The competitiveness of a very simple coin-flipping algorithm is also examined.

In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign tasks to servers, processing online a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The scheduler attempts to keep the load well-balanced. If preemptive reassignments are dissallowed, Azar, Broder and Karlin [3] proved a lower bound of \\Omega\\Gamma p n) on the ratio between the maximum load achieved by an on-line algorithm and the optimum off-line maximum load. We show that this ratio can be greatly reduced by an efficient scheduler using only a small amount of rescheduling. We then apply these ideas to network flow. Cheriyan and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. ...

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.