Fast Algorithms To Partition Simple Rectilinear Polygons* (2009)
Two algorithms to partition hole-free rectilinear polygons are developed. One has complexity ∼ O(kn) and the other O(nlogk) where n is the number of vertices in the polygon and k is the smaller of...
Srijit Kamath, Sartaj Sahni, Jonathan Li, Sanjay Ranka
Abstract. Intensity modulated radiation therapy (IMRT) uses radiation beams of varying intensities to deliver varying doses of radiation to different areas of the tissue. The use of IMRT has allowed...
Two techniques for fast computation of constrained shortest paths (2008)
Shigang Chen, Meongchul Song, Sartaj Sahni
Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In particular,...
Abstract Randomized Routing, Selection, and Sorting on the OTIS-Mesh (2008)
Sanguthevar Rajasekaran, Sartaj Sahni
is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. In this paper we present efficient algorithms for packet routing,sorting,and...
Dynamic Tree Bitmap For IP Lookup and Update ∗ (2008)
We propose a data structure–dynamic tree bitmap–for the representation of dynamic IP router tables that must support very high lookup and update rates. In fact, the dynamic tree bitmap is able to...
Recursively Partitioned Static IP Router-Tables ∗ (2008)
We propose a method–recursive partitioning–to partition a static IP router table so that when each partition is represented using a base structure such as a multibit trie or a hybrid shape...
A Computational Geometry Method for DTOA (2008)
Abstract — We present a computational geometry method for the problem of triangulation in the plane using measurements of distance-differences. Compared to existing solutions to this well-studied...
Two techniques for fast computation of constrained shortest paths (2008)
Shigang Chen, Meongchul Song, Sartaj Sahni
Abstract — Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, MPLS path selection, ATM circuit routing, and traffic engineering. The...
Optimal Field Splitting for Large (2008)
Intensity-modulated Fields, Srijit Kamath, Sartaj Sahni, Sanjay Ranka, Jonathan Li
The multileaf travel range limitations on some linear accelerators require the splitting of a large intensity-modulated field into two or more adjacent abutting intensity-modulated sub-fields. The...
ABSTRACT Long And Short Covering Edges In Combinational Logic Circuits (2008)
Wing Ning Li, Sudhakar M. Reddy, Sartaj Sahni
This paper extends the polynomial time algorithm we obtained in [7] to find a minimal cardinal-ity path set that long covers each lead or gate input of a digital logic circuit. The extension of this...
Two techniques for fast computation of constrained shortest paths (2008)
Shigang Chen, Meongchul Song, Sartaj Sahni
Abstract — Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In...
Sartaj Sahni, Nageshwara Rao, Sanjay Ranka, Yan Li, Eun-sung Jung, Nara Kamath
There has been an increasing number of network deployments that provide dedicated connections through on-demand and in-advance scheduling in support of highperformance applications. We describe...
Two techniques for fast computation of constrained shortest paths (2008)
Shigang Chen, Meongchul Song, Sartaj Sahni
Abstract — Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, MPLS path selection, ATM circuit routing, and traffic engineering. The...
NP-Hard Network Upgrading Problems (2008)
Graphs with delays associated with their edges are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an...
PETCAM–A Power Efficient TCAM For Forwarding Tables ∗ (2008)
We investigate various TCAM architectures recently proposed for TCAM power and memory reduction and show that far better power and memory performance is possible when we use an optimal prefix set for...
A New Weight Balanced Binary Search Tree (2007)
Seonghun Cho And, Seonghun Cho, Sartaj Sahni
We develop a new class of weight balanced binary search trees called fi-balanced binary search trees (fi-BBSTs). fi-BBSTs are designed to have reduced internal path length. As a result, they are...
A Fast Algorithm To Test Planar Topological Routability (2007)
Andrew Lim, Sartaj Sahni, Venkat Thanvantri
We develop a simple linear time algorithm to determine if a collection of two pin nets can be routed, topologically, in a plane (i.e. single layer). Experiments indicate that this algorithm is faster...
A Data Structure for Circular String Analysis and Visualization (2007)
Circular strings are used to represent circular genomes in molecular biology, polygons in computer graphics and computational geometry, and closed curves in computer vision. In this paper we extend...
Biased Leftist Trees and Modified Skip Lists (2007)
We propose the weight biased leftist tree as an alternative to traditional leftist trees [CRAN72] for the representation of mergeable priority queues. A modified version of skip lists [PUGH90] that...
A New Weight Balanced Binary Search Tree (2007)
We develop a new class of weight balanced binary search trees called fi-balanced binary search trees (fi-BBSTs). fi-BBSTs are designed to have reduced internal path length. As a result, they are...
Planar Topological Routing (2007)
Andrew Lim, Venkat Thanvantri, Sartaj Sahni
We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e. single layer). Experiments indicate that this algorithm is faster...
Keywords: OTIS-Hypercube, BPC permutations, diameter Edited by: (2007)
We show that the diameter o an N 2 processor OTIS-Hypercube computer ( N-- 2 d) is 2d q- 1. OTIS-Hypercube algorithms or some commonly perormed permutations-transpose, bit reversal, vector reversal,...
Abstract Anomalies In Parallel Branch-and-Bound Algorithms* (2007)
We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algo-rithm...
Constant Time Convex Hull And Enclosing Box On Reconfigurable Meshes With Buses* (2007)
Madhusudan Nigam, Sartaj Sahni
We develop Ο(1) time algorithms to compute the convex hull and the smallest enclosing box of a set of planar points. Our algorithms are for the reconfigurable mesh with buses architec-ture and run...
Abstract Nearly On Line Scheduling Of Multiprocessor Systems With Memories* (2007)
We show that no multiprocessor system that contains at least one processor with memory size smaller than at least two other processors can be scheduled nearly on line to minimize the finish time. An...
Constant Time ECDF Search And Triangulation On Reconfigurable Meshes With Buses* (2007)
Madhusudan Nigam, Sartaj Sahni
We develop Ο(1) time algorithms to compute the convex hull and the smallest enclosing box of a set of planar points. Our algorithms are for the reconfigurable mesh with buses architec-ture and run...
IP Lookup By Binary Search On Prefix Length * (2007)
Waldvogel et al. [9] have proposed a collection of hash tables (CHT) organization for an IP router table. Each hash table in the CHT contains prefixes of the same length together with markers for...
Minimum Area Joining of Compacted Cells I (2007)
Abstract. We consider the problem of joining a row of compacted cells so as to minimize the area occupied by the cells and the interconnects. The cell joining process includes cell stretching and...
ABSTRACT VIA ASSIGNMENT IN SINGLE ROW ROUTING* (2007)
We examine the via assignment problem that arises when the single row routing approach to the interconnection problem is used. Some new complexity results and two new heuristics are obtained....
A LINEAR ALGORITHMTO FIND A RECTANGULAR DUAL (2007)
We develop an O(n) algorithm to construct a rectangular dual of an n-vertex planar triangulated graph.
Leaf Sequencing Algorithms for Segmented (2007)
Multileaf Collimation, Srijit Kamath, Sartaj Sahni, Jonathan Li, Jatinder Palta
Abstract. The delivery of intensity modulated radiation therapy (IMRT) with a multileaf collimator (MLC) requires the conversion of a radiation fluence map into a leaf sequence file that controls the...
ABSTRACT On Path Selection In Combinational Logic Circuits (2007)
Wing Ning Li, Sudhakar M. Reddy, Sartaj Sahni
In order to ascertain correct operation of digital logic circuits it is necessary to verify correct functional operation as well as correct operation at desired clock rates. To ascertain correct...
Planar Topological Routing * (2007)
Andrew Lim, Venkat Thanvantri, Sartaj Sahni
We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e. single layer). Experiments indicate that this algorithm is faster...
Abstract Preemptive Scheduling Of Uniform Processors With Memory* (2007)
We consider the problem of preemptively scheduling n jobs on a system of m uniform processors. Each job has a release time, a due time, and a memory requirement associated with it. Each pro-cessor...
Optimal Sequencing of Dynamic Multileaf (2007)
Srijit Kamath, Sartaj Sahni, Jatinder Palta
Abstract. Dynamic multileaf collimator (DMLC)-intensity modulated radiation therapy (IMRT) is used to delivery intensity-modulated beams using an MLC, with the leaves in motion. DMLC-IMRT requires...
Supernode binary search tree (2007)
Binary search trees such as red-black trees, AVL trees, and splay trees have been developed for the representation of dictionaries ([5], for example). Suitably modified versions of these data...
A Fast Algorithm for Performance-Driven Selection * Module Implementation (2007)
{yccheng, sahni} cise.ufi.edu
We develop parallel algorithms to compute the Hough transform on a reconfigurable mesh with buses (RMESH) multiprocessor. The p angle Hough transform of an N×N image can be computed in O (plog(N/p))...
We develop a linear time algorithm to determine if a given planar triangulated graph has a rec-tangular dual.
Abstract ODD EVEN SHIFTS IN SIMD HYPERCUBES 1 (2007)
We develop a linear time algorithm to perform all odd (even) length circular shifts of data in an SIMD hypercube. As an application, the algorithm is used to obtain an Ο(M 2 + logN) time and Ο(1)...
We develop a linear time algorithm to determine if a given planar triangulated graph has a rec-tangular dual.
We develop an O (q 2 n + nlogn) algorithm to obtain a preemptive schedule that minimizes max-imum lateness when n jobs with given due dates and memory requirements are to be scheduled on m processors...
ABSTRACT VIA ASSIGNMENT IN SINGLE ROW ROUTING* (2007)
We examine the via assignment problem that arises when the single row routing approach to the interconnection problem is used. Some new complexity results and two new heuristics are obtained....
Abstract Data Structures For IP Lookup With Bursty Access Patterns (2007)
We propose three router-table data structures for the case when the access pattern is bursty. Longest-prefix matching as well as prefix insertion and deletion take £¥¤§¦©¨����� �...
seonghun synop sis. corn and
In the Hypergraph Optimal Linear Arrangement (HOLA) (2007)
We study the problem of arranging circuit components on a straight line so as to minimize the total wire length needed to realize the inter component nets. Branch-and-bound and dynamic pro-gramming...
PROGRAMMINGA HYPERCUBE MULTICOMPUTER (2007)
Sanjay Ranka, Youngju Won, Sartaj Sahni
We describe those features of distributed memory MIMD hypercube multicomputers that are necessary to obtain efficient programs. Several examples are developed. These illustrate the effectiveness of...
Image Transformations on Hypercube and Mesh Multicomputers (2007)
Efficient hypercube and mesh algorithms are developed for the following image transformations: shrinking, expanding, translation, rotation, and scaling. A 2 k −step shrinking and expanding of a...
A LINEAR ALGORITHMTO FIND A RECTANGULAR DUAL (2007)
We develop an O(n) algorithm to construct a rectangular dual of an n-vertex planar triangulated graph.
We define the master-slave multiprocessor scheduling model and provide several applications for the model. O(n log n) algorithms are developed for some of the problems formulated and some others are...
A Fast Algorithm for Transistor Folding * (2007)
2002 Transistor folding reduces the area of row-based designs that employs transistors of different size. Kim and Kang [1] have developed an O(m 2 logm) algorithm to optimally fold m transistor...
We consider fundamental data manipulation operations such as broadcasting, prefix sum, data sum, data shift, data accumulation, consecutive sum, adjacent sum, sorting, and random access reads and...
Abstract Optimal Folding Of Bit Sliced Stacks+ (2007)
We develop fast polynomial time algorithms to optimally fold stacked bit sliced architectures to minimize area subject to height or width constraints. These algorithms may also be applied to folding...
Partitioning 3D Phantoms Into Homogeneous Cuboids * (2007)
Anuj Jain, Sartaj Sahni, Jatinder Palta, James Dempsey
We analyze the heuristic proposed by Jung [3] to partition a 3D phantom into homogeneous cuboids. We show that the 2D version of this heuristic generates the minimum number of rectangles when...
We show that the general two layer constrained via minimization problem and the three layer constrained via minimization problem for HVH topologies are NP-hard. A backtracking and a heuristic...
Optimal Leaf Sequencing with Elimination of (2007)
Srijit Kamath, Sartaj Sahni, Jatinder Palta, Sanjay Ranka
The individual leaves of a multileaf collimator (MLC) have a tongue-andgroove or stepped-edge design to minimize leakage radiation between adjacent leaves. This design element has a drawback that it...
Two techniques for fast computation of constrained shortest paths (2007)
Shigang Chen, Meongchul Song, Sartaj Sahni
Abstract — Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In...
Approximation Algorithms For Wireless Sensor Deployment (2006)
We develop an integer linear programming formulation to find a minimum cost deployment of sensors so at attain desired coverage of a target point set. Additionally ǫ-approximation algorithms and a...
Succinct Representation Of Static Packet Forwarding Tables ∗ (2006)
We develop algorithms for the compact representation of the trie structures that are used for Internet packet forwarding. Our compact representations are experimentally compared with competing...
Succinct representation of static packet classifiers (2006)
We develop algorithms for the compact representation of the 2-dimensional tries that are used for Internet packet classification. Our compact representations are experimentally compared with...
Nearly on Line Scheduling of Multiprocessor Systems with Memories. (2005)
We show that no multiprocessor system that contains at least one processor with memory size smaller than at least two other processors can be scheduled nearly on line to minimize the finish time. An...
A B-tree dynamic router-table design (2005)
We propose B-tree data structures for dynamic router-tables for the cases when the filters are prefixes as well as when they are non-intersecting ranges. A crucial difference between our data...
Maximum Lifetime Routing In Wireless Sensor Networks ∗ (2005)
We show that the problem of routing messages in a wireless sensor network so as to maximize network lifetime is NP-hard. In our model, the online model, each message has to be routed without...
Approximation Algorithms for Multiconstrained Quality-of-Service Routing ∗ (2005)
We propose six new heuristics to find a source-to-destination path that satisfies two or more additive constraints on edge weights. Five of these heuristics become ǫ-approximation algorithms when...
Maximum lifetime broadcasting in wireless networks (2005)
We consider the problem of broadcasting messages in a wireless energy-limited network so as to maximize network lifetime. An O(e log e) algorithm to construct a broadcast tree that maximizes the...
One-Dimensional Packet Classification Using Pipelined Multibit Tries ∗ (2005)
We propose a heuristic for the construction of variable-stride multibit tries. These multibit tries are suitable for one-dimensional packet classification using a pipelined architecture. The...
Conflict detection and resolution in two dimensional prefix router tables (2005)
We show that determining the minimum number of resolve filters that need to be added to a set of 2-dimensional prefix filters so that the filter set can implement a given policy using the...
Algorithms for Wireless Sensor Network (2005)
This paper reviews some of the recent advances in the development of algorithms for wireless sensor networks. We focus on sensor deployment and coverage, routing and sensor fusion.
Packet Classification Using Two-Dimensional Multibit Tries (2005)
We develop fast algorithms to construct space-optimal contrained two-dimensional multibit tries for Internet packet classifier applications. Experimental evidence suggests that using the same memory...
Packet Classification Using Pipelined Two-Dimensional Multibit Tries ∗ (2005)
We propose heuristics for the construction of fixed- and variable-stride two-dimensional multibit tries. These multibit tries are suitable for the classification of Internet packets using a pipelined...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
An O(log n) Dynamic Router-Table Design (2004)
Internet (IP) packet forwarding is typically done by finding the longest prefix in a router table that matches the packer's destination address. For W-bit destination addresses, the use of...
Srijit Kamath, Sartaj Sahni, Sanjay Ranka, Jonathan Li
Abstract. The performances of three recently published leaf sequencing algorithms for step-and-shoot intensity-modulated radiation therapy delivery that eliminate tongue-and-groove underdosage are...
Enhanced interval trees for dynamic IP router-tables (2004)
We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
Efficient construction of multibit tries for IP lookup (2003)
Srinivasan and Varghese [16] have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an O(k * W 2) time dynamic programming algorithm...
A Blocked All-Pairs Shortest-Paths Algorithm (2003)
Gayathri Venkataraman, Sartaj Sahni, Srabani Mukhopadhyaya
Abstract. We propose a blocked version of Floyd's all-pairs shortestpaths algorithm. The blocked algorithm makes better utilization of cache than does Floyd's original algorithm....
o(log n) dynamic router-tables for prefixes and ranges (2003)
Two versions of the Internet (IP) router-table problem are considered. In the first, the router table consists of n pairs of tuples of the form (p, a), where p is an address prefix and a is the...
Efficient construction of pipelined multibit-trie Router-Tables (2003)
Efficient algorithms to construct multibit tries suitable for pipelined router-table applications are developed. We first enhance the 1-phase algorithm of Basu and Narlikar [1] obtaining a 1-phase...
Binary Trees and Parallel Scheduling Algorithms. (2002)
This paper examines the use of binary trees in the design of efficient parallel algorithms. Using binary trees, we develop efficient algorithms for several scheduling problems. The shared memory...
Preemptive Scheduling of a Multiprocessor System with Memories To Minimize L(MAX). (2002)
We develop an O(K(sq)n + nlogn) algorithm to obtain a preemptive schedule that minimizes L sub max when n jobs with given memory requirements are to be scheduled on m processors (n > or = m) of given...
Parallel Scheduling Algorithms. (2002)
We obtain fast parallel algorithms for several scheduling problems. Some of the problems considered are: scheduling to minimize the number of tardy jobs; job sequencing with deadlines; scheduling to...
Optimal BPC Permutations on a Cube Connected SIMD Computer. (2002)
In this paper, we develop an algorithm to perform BPC permutations on a cube connected SIMD computer. The class of BPC permutations includes many of the frequently occurring permutations such as...
Anomalies in Parallel Branch-and-Bound Algorithms. (2002)
Branch-and-bound is a popular algorithm design technique that has been successfully used in the solution of problems that arise in various fields (e.g., combinatorial optimization, artificial...
A Parallel Matching Algorithm for Convex Bipartite Graphs and Applications to Scheduling. (2002)
An efficient parallel algorithm to obtain maximum matching in convex bipartite graphs is obtained. This algorithm can be used to obtain efficient parallel algorithms for several scheduling problems....
Computational geometry on the OTIS-Mesh opto-electronic computer (2002)
We develop efficient algorithms for problems in computational geometry—convex hull, smallest enclosing box, ECDF, two-set dominance, maximal points, all-nearest neighbor, and closest-pair—on the...
Efficient construction of variable-stride multibit tries for IP lookup (2002)
Srinivasan and Varghese [17] have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an £¥¤§ ¦ ©¨�� � ��� �...
Data structures for one-dimensional packet classification using mostspecific-rule matching (2002)
Sartaj Sahni, Kun Suk, Kim Haibin Lu
We review the data structures that have been proposed for one-dimensional packet classification. Our review is limited to data structures for the case when ties among the rules that match an incoming...
In packet classification problem a best matching rule is found for incoming packet using one of the following rule, first matching rule, most specific rule, or highest priority rule. While packet...
Efficient construction of fixed-stride multibit tries for IP lookup (2001)
Srinivasan and Varghese [16] have proposed the use of multibit tries to represent routing tables used for In-ternet (IP) address lookups. They propose an O(k*W 2) time dynamic programming algorithm...
A Fast Algorithm for Transistor Folding (2001)
Transistor folding reduces the area of row-based designs that employ transistors of different size. Kim and Kang [1] have developed an O(m2 log m) algorithm to optimally fold m transistor pairs. In...
The Partitioned Optical Passive Stars Network: Simulations And Fundamental Operations (2000)
We show how a multiprocessor computer interconnected by a partitioned optical passive stars network (POPS) can simulate hypercube and mesh-connected computers. POPS algorithms for data sum, prefix...
Image Processing on the OTIS-Mesh Optoelectronic Computer (2000)
We develop algorithms for histogramming, histogram modification, Hough transform, and image shrinking and expanding on an OTIS-Mesh optoelectronic computer. Our algorithm for the Hough transform is...
Matrix multiplication and data routing using a partitioned optical passive stars network (2000)
We develop optimal or near optimal algorithms to multiply matrices and perform commonly occurring data permutations and BPC permutations on multiprocessor computers interconnected by a partitioned...
Matrix multiplication on the OTIS-Mesh optoelectronic computer (1999)
We develop algorithms to multiply two vectors, a vector and a matrix, and two matrices on an OTIS-Mesh optoelectronic computer. Two mappings, group row and group submesh [25], of a matrix onto an...
Models and algorithms for optical and optoelectronic parallel computers (1999)
This paper briefly reviews some of the more popular parallel-computer models–pipelined optical bus, optical transpose interconnect system (OTIS), and partitioned optical passive stars (POPS)...
A Fast Algorithm for Performance-Driven Module Implementation Selection (1999)
We develop an O(p log n) time algorithm to obtain optimal solutions to the p-pin n-net single channel performance-driven implementation selection problem in which each module has at most two possible...
Preemptive Scheduling of Uniform Processors with Memory. (1998)
We consider the problem of preemptively scheduling n jobs on a system of m uniform processors. Each job has a release time, a due time, and a memory requirement associated with it. Each processor has...
Parallel Generation of Postfix and Tree Forms. (1998)
Efficient parallel algorithms to obtain the postfix and tree forms of an infix arithmetic expression are developed. The shared memory model of parallel computing is used. (Author)
During the course of the contract we developed a model, the master-slave system, to accurately model the scheduling problem that arises when a program running on a host processor initiates many tasks...
Viscoelastic constitutive relations for the steady spinning of a cylinder (1998)
Doowon Paik, Sudhakar Reddy, Sartaj Sahni
We examine the vertex deletion problem for weighted directed acyclic graphs (wdags). The objective is to delete the fewest number of vertices so that the resulting wdag has no path of length> δ....
Basic Operations on the OTIS-Mesh Optoelectronic Computer (1998)
Abstract--In this paper we develop algorithms for some basic operations- broadcast, window broadcast, prefix sum, data sum, rank, shift, data accumulation, consecutive sum, adjacent sum, concentrate,...
Weight biased leftist trees and modified skip lists (1998)
or classroom use is granted without fee provided that copies are not made or dis-tributed for profit or direct commercial advantage and that copies show this notice on the first page or initial...
Randomized routing, selection, and sorting on the otis-mesh (1998)
The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. In this paper we present...
BPC Permutations On The OTIS-Mesh Optoelectronic Computer (1997)
We show that the diameter of an N 2 processor 0TIS-Mesh is 4vf- 3. Two possible embedclings of an N x N mesh onto an 0TIS-Mesh are evaluated. 0TIS-Mesh algorithms for some commonly performed...
Scheduling for distributed computing (1997)
Sartaj Sahni, George Vairaktarakis
A typical model for distributed computing is to have a main program thread that runs on one processor. This thread spawns a number of tasks from timeto-time. When tasks are spawned, they are sent to...
Constant Time Algorithms for Computational Geometry on the Reconfigurable Mesh (1997)
Ju-wook Jang, Madhusudan Nigam, Viktor K. Prasanna, Sartaj Sahni
The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the...
BPC Permutations On The OTIS-Hypercube Optoelectronic Computer (1997)
We show that the diameter of an N 2 processor OTIS-Hypercube computer ( N = 2 d ) is 2d + 1. OTIS-Hypercube algorithms for some commonly performed permutations -- transpose, bit reversal, vector...
Basic Operations On The OTIS-Mesh Optoelectronic Computer (1997)
In this paper we develop algorithms for some basic operations -- broadcast, window broadcast, prefix sum, data sum, rank, shift, data accumulation, consecutive sum, adjacent sum, concentrate,...
Routing on the Array with Reconfigurable Optical Buses (1997)
Sanguthevar Rajasekaran, Ieee Computer Society, Sartaj Sahni
Abstract—In this paper, we present efficient algorithms for sorting, selection, and packet routing on the AROB (Array with Reconfigurable Optical Buses) model. One of our sorting algorithms sorts n...
Optimal folding of standard and custom cells (1996)
Venkat Thanvantri, Sartaj Sahni
We study the problem of folding an ordered list of standard and custom cells into rows of a chip so as to minimize either the routing area or the total chip area. Nine versions of the folding problem...
Parallel computing: Performance metrics and models (1995)
Sartaj Sahni, Venkat Thanvantri
We review the many performance metrics that have been proposed for parallel systems (i.e., program- architecture combinations). These include the many vari-ants of speedup, efficiency, and...
Sorting n 2 numbers on n n meshes (1995)
Madhusudan Nigam, Sartaj Sahni
We show that by folding data from an n × n mesh onto an n × (n /k) submesh, sorting on the submesh, and finally unfolding back onto the entire n × n mesh it is possible to sort on bidirectional...
Parallel Computing: Performance Metrics and Models (1995)
Sartaj Sahni And, Sartaj Sahni, Venkat Thanvantri
We review the many performance metrics that have been proposed for parallel systems (i.e., program -- architecture combinations). These include the many variants of speedup, efficiency, and...
Parallel Computing: Performance Metrics and Models (1995)
Sartaj Sahni, Venkat Thanvantri
We review the many performance metrics that have been proposed for parallel systems (i.e., program -- architecture combinations). These include the many variants of speedup, efficiency, and...
Flipping Modules to Minimize Maximum Wire Length (1995)
We show that obtaining the optimal orientations of modules to minimize the length of the longest wire is NP-hard. If each module is permitted only two possible orientations, this can be done in...
Minimum Area Joining of Compacted Cells (1994)
. We consider the problem of joining a row of compacted cells so as to minimize the area occupied by the cells and the interconnects. The cell joining process includes cell stretching and river...
Folding A Stack Of Equal Width Components (1994)
Venkat Thanvantri, Sartaj Sahni
We consider two versions of the problem of folding a stack of equal width components. In both versions, when a stack is folded, a routing penalty is incurred at the fold. In one version, the height...
Fast Algorithms to Partition Simple Rectilinear Polygons (1994)
Two algorithms to partition hole-free rectilinear polygons are developed. One has complexity ∼ O(kn) and the other O(n log k) where n is the number of vertices in the polygon and k is the smaller...
Image shrinking and expanding on a pyramid (1993)
We develop two algorithms to perform the q step shrinking and expanding of an N×N binary image on a pyramid computer with an N×N base. The time complexity of both algorithms is O(√q). However,...
Reconfigurable mesh algorithms for fundamental data manipulation operations (1993)
algorithms for several fundamental operations are developed. These operations include data
Sorting n Numbers on n × n Reconfigurable Meshes with Buses (1992)
Madhusudan Nigam, Sartaj Sahni
We show how column sort [LEIG85] and rotate sort [MARB88] can be imple-mented on the different reconfigurable mesh with buses (RMB) architectures that have been proposed in the literature. On all of...
Histogramming on a reconfigurable mesh computer (1992)
We develop reconfigurable mesh (RMESH) algorithms for window broadcasting, data shifts, and consecutive sum. These are then used to develop efficient algorithms to compute the histogram of an image...
NP-hard module rotation problems (1992)
University of Florida TR 92-24 Preplaced circuit modules may be rotated to improve performance and/or routability. We show that several simple versions of the module rotation problem are NP-hard.
Flipping Modules to Improve Circuit Performance and Routability (1992)
Preplaced modules may be flipped to improve performance and/or routability. We show that several versions of the module flipping problem are NP-hard. We propose algorithms to obtain module...
Sorting n² Numbers On n × n Meshes (1992)
Madhusudan Nigam, Sartaj Sahni
We show that by folding data from an n × n mesh onto an n × (n / k) submesh, sorting on the submesh, and finally unfolding back onto the entire n × n mesh it is possible to sort on bidirectional...
Constant Time Computational Geometry On Reconfigurable Meshes With Buses (1992)
Madhusudan Nigam, Sartaj Sahni
We develop O(1) time algorithms for the following computational geometry problems: convex hull, smallest enclosing box, ECDF search, and triangulation. Our algorithms are for the reconfigurable mesh...
Sorting n Numbers On n × n Reconfigurable Meshes With Buses (1992)
Madhusudan Nigam, Sartaj Sahni
We show how column sort [LEIG85] and rotate sort [MARB88] can be implemented on the different reconfigurable mesh with buses (RMB) architectures that have been proposed in the literature. On all of...
On the circuit implementation problem (1992)
Wing-ning Li, Andrew Lim, Prathima Agrawal, Sartaj Sahni
Abstract-In this paper, we consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements....
Computing biconnected components on a hypercube (1991)
We describe two hypercube algorithms to find the biconnected components (i.e., blocks) of a connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm. The two hypercube...
Efficient serial and parallel algorithms for median filtering (1991)
We develop a serial algorithm for separable median filtering that requires only two comparisons per element when the window size is three. In addition, fast parallel CREW PRAM algorithms with good...
Reconfigurable mesh algorithms for the area and perimeter of image components (1991)
We consider the following image processing problems: compute the area and perimeter of the components of an image, compute the histogram of an image, and histogram modification. Parallel...
Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our N×N reconfigurable mesh algorithm for...
Jing-fu Jenq, Sartaj Sahni, Prasanna Kumar
Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our NxN reconfigurable mesh algorithm for...
Computing Display Conflicts in String Visualization (1991)
Strings are used to represent a variety of objects such as DNA sequences, text, and numerical sequences. A model for a system for the visualization and analysis of strings was proposed in [1]. In...
Upgrading Circuit Modules To Improve Performance (1991)
We consider the problem of selectively upgrading some of the modules in a circuit so as to meet a specified performance level. The upgrading of a module involves replacing it with an equivalent...
We consider trees, series-parallel digraphs, and general series-parallel digraphs that have vertex weights and delays. The length/delay of a path is the sum of the delays on the path. We show that...
Optimal Folding of Bit Sliced Stacks (1991)
We develop fast polynomial time algorithms to optimally fold stacked bit sliced architectures to minimize area subject to height or width constraints. These algorithms may also be applied to folding...
Convolution on mesh connected multicomputers (1990)
Convolution is an important primitive in computer vision and image processing. In this paper, we present an efficient algorithm for convolution on a mesh connected computer with wra-paround. Our...
Image Template Matching on MIMD hypercube multicomputers (1990)
Efficient algorithms for image template matching on fine grained as well as medium grained MIMD hypercube multicomputers are developed. The medium grained MIMD algorithm is developed specifically for...
String editing on a SIMD hypercube multicomputer (1990)
SIMD hypercube algorithms to determine a minimum cost edit sequence to transform one string into another are developed. If the two strings are of length n, our algorithms take O _____ _ nlogn 2 + n...
Vertex Splitting in Dags and Applications to Partial Scan Designs and Lossy Circuits (1990)
Doowon Paik, Sudhakar Reddy, Sartaj Sahni
Directed acyclic graphs (dags) are often used to model circuits. Path lengths in such dags represent circuit delays. In the vertex splitting problem, the objective is to determine a minimum number of...
Vertex Splitting in Dags and Applications to Partial Scan Designs and Lossy Circuits (1990)
Doowon Paik, Sudhakar Reddy, Sartaj Sahni
Directed acyclic graphs (dags) are often used to model circuits. Path lengths in such dags represent circuit delays. In the vertex splitting problem, the objective is to determine a minimum number of...
String editing on a SIMD hypercube multicomputer (1990)
SIMD hypercube algorithms to determine a minimum cost edit sequence to transform one string into another are developed. If the two strings are of length n, our algorithms take O _____ _ nlogn 2 + log...
Hypercube algorithms for image transformations (1989)
Efficient hypercube algorithms are developed for the following image transformations: shrinking, expanding, translation, rotation, and scaling. A 2 k −step shrinking and expanding of a gray scale...
Hypercube computing: Connected components (1989)
Several approaches to finding the connected components of a graph on a hypercube multicomputer are proposed and analyzed. The results of experiments conducted on an NCUBE hypercube are also...
Two NP-hard interchangeable terminal problems (1988)
Two subproblems that arise when routing channels with interchangeable terminals are shown to be NP-hard. These problems are: P1: Is there a net to terminal assignment that results in an acyclic...
Optimal Linear Arrangement of Circuit Components (1987)
We study the problem of arranging circuit components on a straight line so as to minimize the total wire length needed to realize the inter component nets. Branch-and-bound and dynamic programming...
Raghunath Raghavan, Sartaj Sahni
The single row routing problem is considered. It is shown that the use of backward moves can reduce street congestion when four or more tracks per street are available. We obtain an O((2k)!k*n*log k)...
Manhattan and rectilinear wiring (1981)
Raghunath Raghavan, James Cohoon, Sartaj Sahni
The problem of wiring pairs of points in Manhattan and rectilinear fashion is considered. We develop an Ο(n 2) algorithm to determine whether or not a set of n point pairs can be wired in Manhattan...
The complexity of design automation problems (1980)
Sartaj Sahni, Atul Bhatt, Raghunath Raghavan
This paper reviews several problems that arise in the area of design automation. Most of these problems are shown to be NP-hard. Further, it is unlikely that any of these problems can be solved by...
On the Computational Complexity of Scheme Equivalence (1974)
Constable, Robert L., Sahni, Sartaj
We consider the computational complexity of several decidable problems about program schemes and simple programming languages. In particular, we show that the equivalence problem for Ianov schemes is...
On the Computational Complexity of Scheme Equivalence (1974)
Constable, Robert L., Sahni, Sartaj
We consider the computational complexity of several decidable problems about program schemes and simple programming languages. In particular, we show that the equivalence problem for Ianov schemes is...
On Computing the Determinant of Matrices with Polynomial Entries (1973)
Horowitz, Ellis, Sahni, Sartaj
We consider the problem of computing the determinant of a matrix of polynomials. Four algorithms are compared: expansion by minors, Gaussian elimination over the integers, a method based on...
On Computing the Determinant of Matrices with Polynomial Entries (1973)
Horowitz, Ellis, Sahni, Sartaj
We consider the problem of computing the determinant of a matrix of polynomials. Four algorithms are compared: expansion by minors, Gaussian elimination over the integers, a method based on...
On the Computation of Powers of a Class of Polynomials (1972)
Horowitz, Ellis, Sahni, Sartaj
A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$....
On the Computation of Powers of a Class of Polynomials (1972)
Horowitz, Ellis, Sahni, Sartaj
A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$....
Some Related Problems from Network Flows, Game Theory and Integer Programming (1972)
We consider several important problems for which no polynomially time bounded algorithm is known. These problems are shown to be related in that a polynomial algorithm for one implies a polynomial...
Computing Partitions with Applications to the Knapsack Problem (1972)
Horowitz, Ellis, Sahni, Sartaj
Given $r$ numbers $s_{1}, \ldots, s_{r}$, algorithms are investigated for finding all possible combinations of these numbers which sum to $M$. This problem is a particular instance of the 0-1...
Some Related Problems from Network Flows, Game Theory and Integer Programming (1972)
We consider several important problems for which no polynomially time bounded algorithm is known. These problems are shown to be related in that a polynomial algorithm for one implies a polynomial...
Computing Partitions with Applications to the Knapsack Problem (1972)
Horowitz, Ellis, Sahni, Sartaj
Given $r$ numbers $s_{1}, \ldots, s_{r}$, algorithms are investigated for finding all possible combinations of these numbers which sum to $M$. This problem is a particular instance of the 0-1...