Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Delpratt, O'Neil, Rahman, Naila, Raman, Rajeev
Succinct DOM (SDOM), a DOM implementation, is written in C++, which is suitable for in-memory representation of large static XML documents. SDOM avoids the use of pointers, and is based upon succinct...
Cache Analysis of Non-uniform Distribution Sorting Algorithms (2007)
We analyse the average-case cache performance of distribution sorting algorithms in the case when keys are independently but not necessarily uniformly distributed. The analysis is for both `in-place'...
Raman, Rajeev, Raman, Venkatesh, Satti, Srinivasa Rao
We consider the {\it indexable dictionary} problem, which consists of storing a set $S \subseteq \{0,...,m-1\}$ for some integer $m$, while supporting the operations of $\Rank(x)$, which returns the...
External-Memory Breadth-First Search with Sublinear I/O (2002)
Mehlhorn, Kurt, Meyer, Ulrich, Möhring, Rolf, Raman, Rajeev
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O(...
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons (2002)
Berberich, Eric, Eigenwillig, Arno, Hemmer, Michael, Hert, Susan, Mehlhorn, Kurt, Schömer, Elmar, ...
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal, Pankaj, Hagerup, Torben, Ray, Rahul, Sharir, Micha, Smid, Michiel, Welzl, Emo, ...
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus, Ernst, Bockmayr, Alexander, Elf, Matthias, Kasper, Thomas, Jünger, Michael, Mehlhorn, Kurt, ...
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
Extending Reduction Techniques for the Steiner Tree Problem (2002)
Polzin, Tobias, Vahdati Daneshmand, Siavash, Möhring, Rolf, Raman, Rajeev
On Relaxation Algorithms Based on Markov Random Fields. (1998)
Many computer vision problems can be formulated as computing the minimum energy states of thermal dynamic systems. However, due to the complexity of the energy functions, the solutions to the...
Randomized data structures for the dynamic closest-pair problem (1998)
Golin, Mordecai J., Raman, Rajeev, Schwarz, Christian, Smid, Michiel
We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional...
Three-dimensional acquisition and display system for ultrasonic imaging /--by Rajeev Raman. (1997)
Typescript.
Pre-enhancement of chirp signal for inverse filtering in medical ultrasound (1994)
"Pre-enhancement of chirp signal for inverse filtering in medical ultrasound," Proceedings of the 16th Annual International Conference of IEEE Engineering in Medicine and Biology. Institute of...
Pre-enhancement of chirp signal for inverse filtering in medical ultrasound (1994)
"Pre-enhancement of chirp signal for inverse filtering in medical ultrasound," Proceedings of the 16th Annual International Conference of IEEE Engineering in Medicine and Biology. Institute of...
Very Fast Optimal Parallel Algorithms for Heap Construction (1994)
We give two algorithms for permuting n items in an array into heap order on a CRCW PRAM. The first is deterministic and runs in O(log log n) time and performs O(n) operations. This run-time is the...
Very Fast Optimal Parallel Algorithms for Heap Construction (1994)
We give two algorithms for permuting n items in an array into heap order on a CRCW PRAM. The first is deterministic and runs in O(log log n) time and performs O(n) operations. This run-time is the...
Eliminating Amortization: On Data Structures with Guaranteed Response Time (1992)
Paul F. Dietz, thesis advisor. Thesis (Ph.D.) - Computer Science Department, University of Rochester. Simultaneously published in the Technical Report series.
"October 1992"--Cover.
The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting (1991)
We address the problem of sorting n integers each in the range {l, ... ,m}, for m = n to the O(l), in parallel on the PRAM model of computation. We present a randomized algorithm that runs with very...
Optimal Sub-Logarithmic Time Integer Sorting on the CRCW PRAM (Note) (1991)
Rajasekaran and Reif considered the problem of sorting n integers, each in the range {l, ... , n}, in parallel on the CRCW PRAM, and gave a non-optimal sub-logarithmic time algorithm for this problem...
A Constant Update Time Finger Search Tree (1989)
Levcopolous and Overmars [L088] described a search tree in which the time to insert or delete a key was O(1) once the position of the key to be inserted or deleted was known. Their data structure did...
An Experimental Study of Word-Level Parallelism in Some Sorting Algorithms (1970)
A number of algorithms for fundamental problems such as sorting, searching, priority queues and shortest paths have been proposed recently for the unit-cost RAM with word size w. These algorithms...