The Design and Analysis of Computer Algorithms

By Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. 1974

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, background): “However, we quickly discovered that the O(n2) behavior of these algorithms, at the scale required for verifiable computing, dwarfed the linear number of cryptographic operations (Section 5).”
Practical graph isomorphism, II (2013, background): “ler, 1980) and bounded tree-width (Bodlaender, 1990). The algorithms resulting from this theory are most unlikely to be useful in practice. Only for a very few important graph classes, such as trees (Aho et al., 1974) and planar graphs (Colbourn and Booth, 1981) are there practical approaches which ”
Fast connected-component labeling (2009, methodology): “Another method is an application of the so-called union-find algorithm [18,45–48].”
An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds (1990, background): “However, for large practical problems we propose a randomized version of the algorithm that runs in expected linear time and has a very small time constant (see also [ 1 ]).”
Average Case Analysis of Algorithms on Sequences (2001, methodology): “Undoubtedly, the most popular data structures in algorithms on words are digital trees [3, 269, 305] (e.”
The NP-Completeness Column: An Ongoing Guide (1982, unknown): “I assume that the reader is already familiar with ordinary (sequential) RAM’s (e.g., see [ 2 ]).”
Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems (2005, methodology): “The existing methods for approximating shortest paths based on adding Steiner points [26] which form a grid and subsequently applying Dijkstra's algorithm for finding a shortest path in the grid, provide a complexity bound which depends polynomially on 1//, while the algorithm for the problem in [25”
Frequent Subtree Mining – An Overview (2004, unknown): “Given a rooted unordered tree, its canonical representation based on the pre-order traversal can be obtained in linear time (assuming a ﬁnite alphabet for vertex labels) by adopting Aho’s tree isomorphism algorithm [2], as shown by Luccio et al. [26, 27].”
Trust Management for the Semantic Web (2003, background): “Interestingly, whether or not the aggregation function must be idempotent is the primary difference between Agrawal’s well-formed decomposable path problems [3] and Carre’s path algebra [11] (also related is the definition of a closed semiring in [5]).”
Multiplying matrices faster than coppersmith-winograd (2012, methodology): “…[Extended Abstract] Virginia Vassilevska Williams University of California, Berkeley, and Stanford University virgi@eecs.berkeley.edu ABSTRACT We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction.”