Abstract On External Memory Graph Traversal (2008)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
Abstract On External Memory Graph Traversal (2008)
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
On Reduction via Determinization of Speech-Recognition Lattices (2007)
Adam Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook
We establish a framework for studying the behavior of automatic speech recognition (ASR) lattices (viewed as automata) undergoing determinization. Using this framework, we provide initial insights...
Approximation Algorithms for Restoration Capacity Planning (2007)
Steven J. Phillips, Jeffery R. Westbrook
. A major task of telecommunication network planners is deciding where spare capacity is needed, and how much, so that interrupted traffic may be rerouted in the event of a failure. Planning the...
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs (2002)
Buchsbaum, Adam L., Georgiadis, Loukas, Kaplan, Haim, Rogers, Anne, Tarjan, Robert E., Westbrook, Jeffery R.
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a...
On external memory graph traversal (2000)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
On external memory graph traversal (2000)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
On the Determinization of Weighted Finite Automata (2000)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook
Abstract. We study determinization of weighted finite-state automata (WFAs), which has important applications in automatic speech recognition (ASR). We provide the first polynomial-time algorithm to...
Range Searching Over Tree Cross Products (2000)
Adam L. Buchsbaum, Michael T. Goodrich, Jeffery R. Westbrook
We introduce the tree cross-product problem, which abstracts a data structure common to applications in graph visualization, string matching, and software analysis. We design solutions with a variety...
On The Determinization Of Weighted Finite Automata (2000)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook, R. Westbrook
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...
Future Transport Network Architectures (1999)
Robert D. Doverspike, Robert D. Doverspike, Robert D. Doverspike, Steven Phillips, Steven Phillips, Jeffery R. Westbrook, ...
The architecture of today's long distance transmission networks, which we call the baseline architecture, is a complex and multi-layered hierarchy of Time-Division Multiplexing (TDM) circuits....
A New, Simpler Linear-Time Dominators Algorithm (1999)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
this article is organized as follows. Section 2 outlines Lengauer and Tarjan's approach. Section 3 gives a broad overview of our algorithm and differentiates it from previous work. Section 4...
A Functional Approach to External Graph Algorithms (1999)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
We present a new approach for designing external graph algorithms and use it to design simple deterministic and randomized external algorithms for computing connected components, minimum spanning...
A new, simpler linear-time dominators algorithm (1998)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present a new linear-time algorithm to nd the immediate dominators of all vertices in a owgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
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...
A Functional Approach to External Graph Algorithms (1998)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
Abstract. We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected components, minimum spanning trees, bottleneck...
Shrinking Language Models by Robust Approximation (1998)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook
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...
A Functional Approach to External Graph Algorithms (1998)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
We present a new approach for designing external graph algorithms and use it to design simple deterministic and randomized external algorithms for computing connected components, minimum spanning...
A New, Simpler Linear-Time Dominators Algorithm (1998)
Adam Buchsbaum Haim, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
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: we combine the use of microtrees...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
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...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
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...
Algorithms and data structures for dynamic graph problems / (1989)
Thesis (Ph. D.)--Princeton University, 1989.