An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture (2006)
Brodnik, Andrej, Karlsson, Johan, Munro, J. Ian, Nilsson, Andreas
In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which...
Fun-Sort --- Or the Chaos of Unordered (2004)
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n log n). If n...
On the arrangement of cliques in chordal graphs with respect to the cuts (2004)
Chandran, L. Sunil, Narayanaswamy, N.S., Chwa, Kyung-Yong, Munro, J. Ian
Efficient Generation of Uniform Samples from Phylogenetic Trees (2003)
Paul Kearney, J. Ian Munro, Derek Phillips, Caprion Pharmaceuticals
In this paper, we introduce new algorithms for selecting taxon (leaf) samples from large phylogenetic trees, uniformly at random, under certain biologically relevant constraints on the taxa. All the...
Efficient Tree Layout in a Multilevel Memory Hierarchy (2003)
Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-colton, J. Ian Munro, Theis Rauhe, ...
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed during a search along a...
Alcom-FT Technical Report Series (2003)
Gerth Stlting Brodal, Erik D. Demaine, J. Ian Munro
We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates blocks...
Fun-Sort --- Or the Chaos of Unordered (2003)
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n log n). If n...
Nicholas J. A. Harvey, J. Ian Munro
We present the first deterministic, scalable overlay network. In contrast, most overlay networks use hashing or randomization to achieve a uniform distribution of data and routing traffic.
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Efficient Visibility Queries in Simple Polygons (2002)
We present a method of decomposing a simple polygon that allows the preprocessing of the polygon to eciently answer visibility queries of various forms in an output sensitive manner.
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Cache-Oblivious Priority Queue and Graph Algorithm Applications (2002)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-minkley, J. Ian Munro
queue data structure, supporting insertion, deletion, and B ) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory...
The Complexity of Clickomania (2001)
Biedl, Therese C., Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf, Jacobsen, Lars, Munro, J. Ian
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Space Efficient Suffix Trees (2001)
J. Ian Munro, S. Srinivasa Rao
We give the first representation of a suffix tree that uses n lg n+O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet)in O(m) time, where n...
The Complexity of Clickomania (2001)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Faith E. Fich, J. Ian Munro, Patricio V. Poblete
We address the fundamental problem of permuting the elements of an array of n elements according to some given permutation. Our goal is to perform the permutation quickly using only a polylogarithmic...
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, J. Ian Munro
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
Biedl, Therese, Chan, Timothy, Demaine, Erik D., Fleischer, Rudolf H., Golin, Mordecai J., Munro, J. Ian
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
On Universally Easy Classes for NP-complete Problems (2000)
We explore the natural question of whether all NP- complete problems have a common restriction under which they are polynomially solvable. More precisely, we study what languages are universally easy...
Worst Case Constant Time Priority Queue (2000)
Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro
We present a new data structure of size 3M +o(M) bits for solving
Adaptive Set Intersections, Unions, and Differences (2000)
Motivated by boolean queries in text database systems, we consider the problems of finding the intersection, union, or difference of a collection of sorted sets. While the worst-case complexity of...
Resizable Arrays in Optimal Time and Space (2000)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick
. We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l::l + n Gamma 1], of fixed-size elements, as elements are...
Online Routing in Convex Subdivisions (2000)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
On the Competitiveness of Linear Search (2000)
We re-examine offline techniques for linear search. Under a reasonable model of computation, a method is given to perform offline linear search in amortized cost proportional to the entropy of the...
Fast Allocation and Deallocation with an Improved Buddy System (1999)
. We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates...
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds (1997)
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
. We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear...
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds (1997)
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
. We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear...
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds (1997)
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
. We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear...
. We address the problem of a succinct static data structure representing points on an M Theta M grid (M = 2 m where m is size of a word) that permits to answer the question of finding the closest...
Membership in Constant Time and Minimum Space (1995)
. We investigate the problem of storing a subset of the elements of a boundeduniverse so that searches canbe performed in constant time and the space used is within a constant factor of the minimum...
Online Routing in Convex Subdivisions (1970)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Pat Morin, J. Ian Munro
. We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...