Sorting under Partial Information (without the Ellipsoid Algorithm) (2009)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël, Munro, J. Ian
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and...
Fast Allocation and Deallocation with an Improved Buddy System ∗ (2008)
Gerth Stølting 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...
An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture (2008)
Andrej Brodnik, Johan Karlsson, J. Ian Munro
No Institute Given Abstract. 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...
Roberto Grossi, J. Ian Munro, Linda Pagli
Abstract We reopen the issue of finding an implicit data struc-ture for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n lo-cations of an...
An Efficient Algorithm for Partial Order Production (2008)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël M., Munro, J. Ian
We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special...
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick
Abstract 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...
An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture (2008)
Andrej Brodnik, Johan Karlsson, J. Ian Munro, Andreas Nilsson
Abstract. 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...
DOI: 10.1007/s00453-004-1146-6 Representing Trees of Higher Degree 1 (2008)
David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao
Abstract. This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our...
Walter Cunto, J. Ian Munro, Manuel Rey
The median, the 0·25-percentile and the 0·75-percentile are three of the moat relevant ranks in data analysis. MED2Q is a new in situ algorithm to solve this problem. It asymptotically performs an...
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...
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...
Lars Arge, Michael A. Bender, Erik D. Demaine, J. Ian Munro
In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O( 1 B log M=B
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.
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...
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...
Efficient Generation of Uniform Samples from Phylogenetic Trees (2007)
Paul Kearney, J. Ian Munro, Derek Phillips
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...
Fun-Sort --- Or the Chaos of Unordered (2007)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
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...
An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms (2007)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers,...
Experimental Evaluation of List Update Algorithms for Data Compression (2007)
Reza Dorrigiv, Ro López-ortiz, J. Ian Munro
Abstract. List update algorithms have been widely used as subroutines in compression schemas, specially after the introduction of the Burrows-Wheeler transform. The Burrows-Wheeler transform (BWT),...
Succinct indexes for strings, binary relations and multi-labeled trees (2007)
Jérémy Barbay, Meng He, J. Ian Munro, S. Srinivasa Rao
We define and design succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures called succinct indexes that occupy asymptotically less space than the...
The binomial transform and the analysis of skip lists (2006)
Poblete, Patricio V., Munro, J. Ian, Papadakis, Thomas
To any sequence of real numbers < a(n)>(n >= 0), we can associate another sequence < a(s)>(s >= 0), which Knuth calls its binomial transform. This transform is defined through the rule as = Bsan =...
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...
Towards Optimal Multiple Selection (2005)
Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders, Peter S
The multiple selection problem asks for the elements of rank r1 , r2 , . . . , rk from a linearly ordered set of n elements. Let B denote the information theoretic lower bound on the number of...
Towards optimal multiple selection (2005)
Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter S
Abstract. The multiple selection problem asks for the elements of rank r1, r2,..., rk from a linearly ordered set of n elements. Let B denote the information theoretic lower bound on the number of...
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
Identifying frequent items in sliding windows over on-line packet streams (2003)
Lukasz Golab, Alejandro López-ortiz, David Dehaan, J. Ian Munro
Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring...
Identifying frequent items in sliding windows over on-line packet streams (2003)
Lukasz Golab, Alejandro López-ortiz, David Dehaan, J. Ian Munro
Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring...
Fast Allocation and Deallocation with an Improved Buddy System (2003)
Gerth Stølting 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...
We present a deterministic scalable overlay network. In contrast, most previous overlay networks use randomness or hashing (pseudo-randomness) to achieve a uniform distribution of data and routing...
Frequency estimation of internet packet streams with limited space (2002)
Erik D. Demaine, Ro López-ortiz, J. Ian Munro
Abstract. We consider a router on the Internet analyzing the statistical properties of a TCP/IP packet stream. A fundamental difficulty with measuring traffic behavior on the Internet is that there...
Robot localization without depth perception (2002)
Erik D. Demaine, Ro López-ortiz, J. Ian Munro
Abstract. Consider the problem of placing reflectors in a 2-D environment in such a way that a robot equipped with a basic laser can always determine its current location. The robot is allowed to...
Cache-oblivious priority queue and graph algorithm applications (2002)
Lars Arge, Bryan Holland-minkley, Michael A. Bender, J. Ian Munro, Erik D. Demaine
In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 B logM/B N) amortized memory B transfers, where M...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
Abstract. 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...
Frequency estimation of internet packet streams with limited space (2002)
Abstract. We consider a router on the Internet analyzing the statistical properties of a TCP/IP packet stream. A fundamental difficulty with measuring traffic behavior on the Internet is that there...
The complexity of Clickomania (2002)
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...
Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)
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...
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...
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...
Worst case constant time priority queue (2001)
Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro
We present a new data structure of size O(M) for solving the vEB problem. When this data structure is used in combination with a new memory topology it provides an O(1) worst case time solution. 1
Worst case constant time priority queue (2001)
Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro
We present a new data structure of size 3M + o(M) bits for solving the "discrete priority queue " problem. When this data structure is used in combination with a new memory topology...
The Complexity of Clickomania (2001)
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...
Worst case constant time priority queue (2001)
Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro
We present a new data structure of size 3M +o(M) bits for solving the "discrete priority queue " problem. When this data structure is used in combination with a new memory topology...
On universally easy classes for NP-complete problems (2001)
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...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, ...
. 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...
Adaptive Set Intersections, Unions, and Differences (2000)
Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro
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...
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...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose Andrej, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, ...
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...
Fast Allocation and Deallocation with an Improved Buddy System (1999)
Abstract. 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...
Resizable Arrays in Optimal Time and Space (1999)
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...
Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs (1999)
J. Ian Munro, Venkatesh Raman, J. Ian, Munro Venkatesh Raman
We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree and balanced parenthesis expression. Our representations use an amount of space within a...
Fast Allocation and Deallocation with an Improved Buddy System (1999)
Abstract. We propose several modi cations to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and...
Lower Bounds, Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
et al.: Trans-Dichotomous
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 (1997)
Lower Bounds, Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro, Andrej Brodnik, Peter Bro Miltersen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
. 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...
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...
Membership in Constant Time and Minimum Space (1994)
. 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...
Fun-Sort --- Or the Chaos of Unordered (1994)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
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...