@article {14976,
	title = {Interactive direct volume rendering on desktop multicore processors},
	journal = {Concurrency and Computation: Practice and Experience},
	volume = {21},
	year = {2009},
	month = {2009/09/10/},
	pages = {2199 - 2212},
	abstract = {We present a new multithreaded implementation for the computationally demanding direct volume rendering (DVR) of volumetric data sets on desktop multicore processors using ray casting. The new implementation achieves interactive rendering of very large volumes, even on high resolution screens. Our implementation is based on a new algorithm that combines an object-order traversal of the volumetric data followed by a focused ray casting. Using a very compact data structure, our method starts with a quick association of data subcubes with fine-grain screen tiles appearing along the viewing direction in front-to-back order. The next stage uses very limited ray casting on the generated sets of subcubes while skipping empty or transparent space and applying early ray termination in an effective way. Our multithreaded implementation makes use of new dynamic techniques to ensure effective memory management and load balancing. Our software enables a user to interactively explore large data sets through DVR while arbitrarily specifying a 2D transfer function. We test our system on a wide variety of well-known volumetric data sets on a two-processor Clovertown platform, each consisting of a Quad-Core 1.86 GHz Intel Xeon Processor. Our experimental tests demonstrate DVR at interactive rates for the largest data sets that can fit in the main memory on our platform. These tests also indicate a high degree of scalability, excellent load balancing, and efficient memory management across the data sets used. Copyright {\textcopyright} 2009 John Wiley \& Sons, Ltd.},
	keywords = {direct volume rendering, multicore processors, multithreaded algorithms, Parallel algorithms, volume visualization},
	isbn = {1532-0634},
	doi = {10.1002/cpe.1485},
	url = {http://onlinelibrary.wiley.com/doi/10.1002/cpe.1485/abstract?userIsAuthenticated=false\&deniedAccessCustomisedMessage=},
	author = {Wang,Qin and JaJa, Joseph F.}
}
@conference {17996,
	title = {Fpga-based prototype of a pram-on-chip processor},
	booktitle = {Proceedings of the 5th conference on Computing frontiers},
	series = {CF {\textquoteright}08},
	year = {2008},
	month = {2008///},
	pages = {55 - 66},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {PRAM (Parallel Random Access Model) has been widely regarded a desirable parallel machine model for many years, but it is also believed to be "impossible in reality." As the new billion-transistor processor era begins, the eXplicit Multi-Threading (XMT) PRAM-On-Chip project is attempting to design an on-chip parallel processor that efficiently supports PRAM algorithms. This paper presents the first prototype of the XMT architecture that incorporates 64 simple in-order processors operating at 75MHz. The microarchitecture of the prototype is described and the performance is studied with respect to some micro-benchmarks. Using cycle accurate emulation, the projected performance of an 800MHz XMT ASIC processor is compared with AMD Opteron 2.6GHz, which uses similar area as would a 64-processor ASIC version of the XMT prototype. The results suggest that an only 800MHz XMT ASIC system outperforms AMD Opteron 2.6GHz, with speedups ranging between 1.57 and 8.56.},
	keywords = {ease-of-programming, explicit multi-threading, on-chip parallel processor, Parallel algorithms, PRAM, XMT},
	isbn = {978-1-60558-077-7},
	doi = {10.1145/1366230.1366240},
	url = {http://doi.acm.org/10.1145/1366230.1366240},
	author = {Wen,Xingzhi and Vishkin, Uzi}
}
@conference {18001,
	title = {PRAM-on-chip: first commitment to silicon},
	booktitle = {Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures},
	series = {SPAA {\textquoteright}07},
	year = {2007},
	month = {2007///},
	pages = {301 - 302},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	keywords = {ease-of-programming, explicit multi-threading, on-chip parallel processor, Parallel algorithms, PRAM, XMT},
	isbn = {978-1-59593-667-7},
	doi = {10.1145/1248377.1248427},
	url = {http://doi.acm.org/10.1145/1248377.1248427},
	author = {Wen,Xingzhi and Vishkin, Uzi}
}
@conference {18025,
	title = {Two techniques for reconciling algorithm parallelism with memory constraints},
	booktitle = {Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
	series = {SPAA {\textquoteright}02},
	year = {2002},
	month = {2002///},
	pages = {95 - 98},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {The utility of algorithm parallelism for coping with increased processor to memory latencies using "latency hiding" is part of the folklore of parallel computing. Latency hiding techniques increase the traffic to memory and therefore may "hit another wall": limited bandwidth to memory. The current paper attempts to stimulate research in the following general direction: show that algorithm parallelism need not conflict with limited bandwidth.A general technique for using parallel algorithms to enhance serial implementation in the face of processor-memory latency problems is revisited. Two techniques for alleviating memory bandwidth constraints are presented. Both techniques can be incorporated in a compiler.There is often considerable parallelism in many of the algorithms which are known as useful serial algorithms. Interestingly enough, all the examples provided for the use of the two techniques come from such serial algorithms.},
	keywords = {memory systems constraints, Parallel algorithms, prefetching},
	isbn = {1-58113-529-7},
	doi = {10.1145/564870.564884},
	url = {http://doi.acm.org/10.1145/564870.564884},
	author = {Vishkin, Uzi}
}
@conference {17599,
	title = {Finding large independent sets of hypergraphs in parallel},
	booktitle = {Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures},
	series = {SPAA {\textquoteright}01},
	year = {2001},
	month = {2001///},
	pages = {163 - 168},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound \&agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size \&agr;k (H). They also show that \&agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size \&agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.},
	keywords = {hypergraphs, independent sets, Parallel algorithms, randomized algorithms},
	isbn = {1-58113-409-6},
	doi = {10.1145/378580.378622},
	url = {http://doi.acm.org/10.1145/378580.378622},
	author = {Shachnai,Hadas and Srinivasan, Aravind}
}
@article {17603,
	title = {Improved Algorithms via Approximations of Probability Distributions},
	journal = {Journal of Computer and System Sciences},
	volume = {61},
	year = {2000},
	month = {2000/08//},
	pages = {81 - 107},
	abstract = {We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veli{\v c}kovi{\'c}.},
	keywords = {derandomization, discrepancy, explicit constructions, graph coloring, Parallel algorithms, small sample spaces},
	isbn = {0022-0000},
	doi = {10.1006/jcss.1999.1695},
	url = {http://www.sciencedirect.com/science/article/pii/S0022000099916951},
	author = {Chari,Suresh and Rohatgi,Pankaj and Srinivasan, Aravind}
}
@article {15024,
	title = {Simple: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMPs)},
	journal = {Journal of Parallel and Distributed Computing},
	volume = {58},
	year = {1999},
	month = {1999/07//},
	pages = {92 - 108},
	abstract = {We describe a methodology for developing high performance programs running on clusters of SMP nodes. The SMP cluster programming methodology is based on a small prototype kernel (Simple) of collective communication primitives that make efficient use of the hybrid shared and message-passing environment. We illustrate the power of our methodology by presenting experimental results for sorting integers, two-dimensional fast Fourier transforms (FFT), and constraint-satisfied searching. Our testbed is a cluster of DEC AlphaServer 2100 4/275 nodes interconnected by an ATM switch.},
	keywords = {cluster computing, communication primitives, experimental parallel algorithms, message passing (MPI), Parallel algorithms, parallel performance, shared memory, symmetric multiprocessors (SMP)},
	isbn = {0743-7315},
	doi = {10.1006/jpdc.1999.1541},
	url = {http://www.sciencedirect.com/science/article/pii/S0743731599915411},
	author = {Bader,David A. and JaJa, Joseph F.}
}
@article {14770,
	title = {Critical path profiling of message passing and shared-memory programs},
	journal = {IEEE Transactions on Parallel and Distributed Systems},
	volume = {9},
	year = {1998},
	month = {1998/10//},
	pages = {1029 - 1040},
	abstract = {We introduce a runtime, nontrace-based algorithm to compute the critical path profile of the execution of message passing and shared-memory parallel programs. Our algorithm permits starting or stopping the critical path computation during program execution and reporting intermediate values. We also present an online algorithm to compute a variant of critical path, called critical path zeroing, that measures the reduction in application execution time that improving a selected procedure will have. Finally, we present a brief case study to quantify the runtime overhead of our algorithm and to show that online critical path profiling can be used to find program bottlenecks},
	keywords = {Computer Society, Concurrent computing, critical path computation, critical path profile, critical path zeroing, distributed processing, distributed shared memory systems, Instruments, Message passing, Monitoring, online algorithm, online critical path profiling, Parallel algorithms, program bottlenecks, Runtime, runtime nontrace-based algorithm, runtime overhead, shared-memory programs, system monitoring, Time measurement, Yarn},
	isbn = {1045-9219},
	doi = {10.1109/71.730530},
	author = {Hollingsworth, Jeffrey K}
}
@conference {17609,
	title = {Improved bounds and algorithms for hypergraph two-coloring},
	booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings},
	year = {1998},
	month = {1998/11/08/11},
	pages = {684 - 693},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma},
	keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability},
	isbn = {0-8186-9172-7},
	doi = {10.1109/SFCS.1998.743519},
	author = {Radhakrishnan,J. and Srinivasan, Aravind}
}
@article {14931,
	title = {A new deterministic parallel sorting algorithm with an experimental evaluation},
	journal = {Journal of Experimental Algorithmics (JEA)},
	volume = {3},
	year = {1998},
	month = {1998/09//},
	abstract = {We introduce a new deterministic parallel sorting algorithm for distributed memory machines based on the regular sampling approach. The algorithm uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. Moreover, unlike previous variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. This algorithm was implemented in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2-WN, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, the performance compares closely to that of our random sample sort algorithm, which seems to outperform all similar algorithms known to the authors on these platforms. Together, their performance is nearly invariant over the set of input distributions, unlike previous efficient algorithms. However, unlike our randomized sorting algorithm, the performance and memory requirements of our regular sorting algorithm can be deterministically guaranteed.},
	keywords = {generalized sorting, integer sorting, Parallel algorithms, parallel performance, sorting by regular sampling},
	isbn = {1084-6654},
	doi = {10.1145/297096.297128},
	url = {http://doi.acm.org/10.1145/297096.297128},
	author = {Helman,David R. and JaJa, Joseph F. and Bader,David A.}
}
@article {14936,
	title = {A Randomized Parallel Sorting Algorithm with an Experimental Study},
	journal = {Journal of Parallel and Distributed Computing},
	volume = {52},
	year = {1998},
	month = {1998/07/10/},
	pages = {1 - 23},
	abstract = {Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. Moreover, unlike previous variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare favorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark.},
	keywords = {generalized sorting, integer sorting, sample sort, parallel performance, Parallel algorithms},
	isbn = {0743-7315},
	doi = {10.1006/jpdc.1998.1462},
	url = {http://www.sciencedirect.com/science/article/pii/S0743731598914629},
	author = {Helman,David R. and Bader,David A. and JaJa, Joseph F.}
}
@article {15009,
	title = {Parallel algorithms for image histogramming and connected components with an experimental study (extended abstract)},
	journal = {ACM SIGPLAN Notices},
	volume = {30},
	year = {1995},
	month = {1995/08//},
	pages = {123 - 133},
	abstract = {This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and connected components. Our general framework is a single-address space, distributed memory programming model. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. Our connected components algorithm uses a novel approach for parallel merging which performs drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. The algorithms have been coded in Split-C and run on a variety of platforms. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for  these two primitives, even when compared with machine-specific implementations. More efficient implementations of Split-C will likely result in even faster execution times.},
	keywords = {connected components, histogramming, IMAGE PROCESSING, image understanding, Parallel algorithms, scalable parallel processing},
	isbn = {0362-1340},
	doi = {10.1145/209937.209950},
	url = {http://doi.acm.org/10.1145/209937.209950},
	author = {Bader,David A. and JaJa, Joseph F.}
}
@conference {17660,
	title = {Splitters and near-optimal derandomization},
	booktitle = {, 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings},
	year = {1995},
	month = {1995/10/23/25},
	pages = {182 - 191},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits},
	keywords = {Boosting, Circuit testing, computational complexity, computational linguistics, Computer science, Contracts, derandomization, deterministic constructions, Educational institutions, Engineering profession, exhaustive testing, fairly general method, fixed-subgraph finding algorithms, hardness of approximation, Information systems, k-restrictions, learning, local-coloring protocol, MATHEMATICS, near-optimal constructions, near-optimal derandomization, Parallel algorithms, probabilistic bound, probability, Protocols, randomised algorithms, Set cover, splitters},
	isbn = {0-8186-7183-1},
	doi = {10.1109/SFCS.1995.492475},
	author = {Naor,M. and Schulman,L. J and Srinivasan, Aravind}
}
@article {15214,
	title = {On the parallel complexity of digraph reachability},
	journal = {Information Processing Letters},
	volume = {52},
	year = {1994},
	month = {1994/12/09/},
	pages = {239 - 241},
	abstract = {We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.},
	keywords = {combinatorial problems, Parallel algorithms},
	isbn = {0020-0190},
	doi = {10.1016/0020-0190(94)00153-7},
	url = {http://www.sciencedirect.com/science/article/pii/0020019094001537},
	author = {Khuller, Samir and Vishkin, Uzi}
}
@conference {14579,
	title = {A SIMD solution to the sequence comparison problem on the MGAP},
	booktitle = {International Conference on Application Specific Array Processors, 1994. Proceedings},
	year = {1994},
	month = {1994/08/22/24},
	pages = {336 - 345},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128},
	keywords = {AT-optimal algorithm, Biological information theory, biology computing, biosequence comparison problem, computational complexity, Computer science, Costs, database size, Databases, DNA computing, dynamic programming, dynamic programming algorithms, fine-grained massively parallel processor array, Genetics, Heuristic algorithms, maximally similar sequence, MGAP parallel computer, Micro-Grain Array Processor, Military computing, molecular biology, molecular biophysics, Nearest neighbor searches, nearest-neighbor connections, Parallel algorithms, pipeline processing, pipelined SIMD solution, sequence alignment problem, sequences},
	isbn = {0-8186-6517-3},
	doi = {10.1109/ASAP.1994.331791},
	author = {Borah,M. and Bajwa,R. S and Hannenhalli, Sridhar and Irwin,M. J}
}
@article {15042,
	title = {Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima},
	journal = {SIAM Journal on Computing},
	volume = {23},
	year = {1994},
	month = {1994///},
	pages = {449 - 465},
	abstract = {A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size $n$, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ *  n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $\Omega (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348{\textendash}355].The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ *  n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.
},
	keywords = {Parallel algorithms, pram algorithms, prefix minima, VLSI routing},
	doi = {10.1137/S0097539791218275},
	url = {http://link.aip.org/link/?SMJ/23/449/1},
	author = {Berkman,Omer and JaJa, Joseph F. and Krishnamurthy,Sridhar and Thurimella,Ramakrishna and Vishkin, Uzi}
}
@article {14111,
	title = {Parallel sparse Cholesky factorization on a shared memory multiprocessor},
	journal = {Parallel Computing},
	volume = {18},
	year = {1992},
	month = {1992/09//},
	pages = {1009 - 1022},
	abstract = {Parallel implementations of Cholesky factorization for sparse symmetric positive definite matrices are considered on a shared memory multiprocessor computer. Two column-oriented schemes, known as the column-Cholesky algorithm and the fan-in algorithm, along with enhancements of each, are implemented and discussed. High parallel efficiency of the column-Cholesky algorithm and its enhancement is demonstrated for test problems. A detailed investigation of the performance of the fan-in algorithm and its enhancement, the compute-ahead fan-in algorithm, is made to study the effects of overhead associated with the fan-in based schemes.},
	keywords = {linear algebra, Parallel algorithms, shared memory multiprocessor, sparse Cholesky factorization},
	isbn = {0167-8191},
	doi = {16/0167-8191(92)90014-X},
	url = {http://www.sciencedirect.com/science/article/pii/016781919290014X},
	author = {Zhang, G. and Elman, Howard}
}
@article {15006,
	title = {Parallel Algorithms for Channel Routing in the Knock-Knee Model},
	journal = {SIAM Journal on Computing},
	volume = {20},
	year = {1991},
	month = {1991///},
	pages = {228 - 245},
	abstract = {The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. A new approach to route all the nets within $d$ tracks, where $d$ is the density, such that the corresponding layout can be realized with three layers is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$.},
	keywords = {channel routing, Layout, left-edge algorithm, line packing, Parallel algorithms, VLSI design},
	doi = {10.1137/0220014},
	url = {http://link.aip.org/link/?SMJ/20/228/1},
	author = {JaJa, Joseph F. and Chang,Shing-Chong}
}
@article {15012,
	title = {Parallel algorithms for VLSI routing},
	journal = {Integration, the VLSI Journal},
	volume = {12},
	year = {1991},
	month = {1991/12//},
	pages = {305 - 320},
	abstract = {With the increase in the design complexity of VLSI systems, there is an ever increasing need for efficient design automation tools. Parallel processing could open up the way for substantially faster and cost-effective VLSI design tools. In this paper, we review some of the basic parallel algorithms that have been recently developed to handle problems arising in VLSI routing. We also include some results that have not appeared in the literature before. These results indicate that existing parallel algorithmic techniques can efficiently handle many VLSI routing problems. Our emphasis will be on outlining some of the basic parallel strategies with appropriate pointers to the literature for more details.},
	keywords = {channel routing, detailed routing, global routing, Parallel algorithms, river routing, VLSI routing},
	isbn = {0167-9260},
	doi = {10.1016/0167-9260(91)90027-I},
	url = {http://www.sciencedirect.com/science/article/pii/016792609190027I},
	author = {JaJa, Joseph F.}
}
@conference {14575,
	title = {Parallel transitive closure computations using topological sort},
	booktitle = {, Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991},
	year = {1991},
	month = {1991/12/04/6},
	pages = {122 - 129},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm},
	keywords = {Computer science, Concurrent computing, data partitioning, Database systems, database theory, deductive databases, File systems, horizontal partitioning, joins, local data fragments, message passing multiprocessor system, Multiprocessing systems, Parallel algorithms, PARALLEL PROCESSING, parallel programming, parallel transitive closure, processing nodes, relation tuples, Relational databases, sorting, topological sort},
	isbn = {0-8186-2295-4},
	doi = {10.1109/PDIS.1991.183079},
	author = {Hua,K. A and Hannenhalli, Sridhar}
}
@article {16768,
	title = {A pipeline N-way join algorithm based on the 2-way semijoin program},
	journal = {IEEE Transactions on Knowledge and Data Engineering},
	volume = {3},
	year = {1991},
	month = {1991/12//},
	pages = {486 - 495},
	abstract = {The semijoin has been used as an effective operator in reducing data transmission and processing over a network that allows forward size reduction of relations and intermediate results generated during the processing of a distributed query. The authors propose a relational operator, two-way semijoin, which enhanced the semijoin with backward size reduction capability for more cost-effective query processing. A pipeline N-way join algorithm for joining the reduced relations residing on N sites is introduced. The main advantage of this algorithm is that it eliminates the need for transferring and storing intermediate results among the sites. A set of experiments showing that the proposed algorithm outperforms all known conventional join algorithms that generate intermediate results is included},
	keywords = {2-way semijoin program, backward size reduction, Bandwidth, Computer networks, Costs, Data communication, data transmission, Database systems, database theory, Delay, distributed databases, distributed query, forward size reduction, intermediate results, Local area networks, network, Parallel algorithms, pipeline N-way join algorithm, pipeline processing, Pipelines, programming theory, Query processing, Relational databases, relational operator, SITES, Workstations},
	isbn = {1041-4347},
	doi = {10.1109/69.109109},
	author = {Roussopoulos, Nick and Kang,H.}
}
@conference {18145,
	title = {Towards a theory of nearly constant time parallel algorithms},
	booktitle = {Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on},
	year = {1991},
	month = {1991/10//},
	pages = {698 - 710},
	abstract = {It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of <e1>O</e1>(lg* <e1>n</e1>) (nearly-constant), with high probability, is achieved using <e1>n</e1>/lg* <e1>n</e1> (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using <e1>n</e1> processors, approximates the sum of <e1>n</e1> positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones},
	keywords = {computational complexity, Estimation, nearly constant time parallel algorithms, Parallel algorithms, positive numbers, randomization, running time, superfast optimal algorithms},
	doi = {10.1109/SFCS.1991.185438},
	author = {Gil,J. and Matias,Y. and Vishkin, Uzi}
}
@article {15203,
	title = {Coloring algorithms for K5-minor free graphs},
	journal = {Information Processing Letters},
	volume = {34},
	year = {1990},
	month = {1990/04/24/},
	pages = {203 - 208},
	abstract = {In this paper we give an NC algorithm to five color K5-minor free graphs. We also give a polynomial time algorithm to obtain a four coloring for a K5-minor free graph.},
	keywords = {graph minor, Parallel algorithms, planar graph coloring},
	isbn = {0020-0190},
	doi = {10.1016/0020-0190(90)90161-P},
	url = {http://www.sciencedirect.com/science/article/pii/002001909090161P},
	author = {Khuller, Samir}
}
@conference {16655,
	title = {Parallel set covering algorithms},
	booktitle = {Artificial Intelligence Applications, 1988., Proceedings of the Fourth Conference on},
	year = {1988},
	month = {1988/03//},
	pages = {274 - 279},
	abstract = {The authors develop some parallel algorithms for set covering. A brief introduction is given into the parsimonious set covering theory, and algorithms using one type of parsimony called irredundancy are developed. They also discuss several machine-independent parallel constructs that are used to express the parallel algorithms. The algorithms were tested on the Butterfly parallel processor system. The authors present some of the tests conducted and their analyses. Finally, the merits and limitations of the algorithms that were identified during the tests are presented},
	keywords = {Butterfly parallel processor system, irredundancy, Parallel algorithms, parsimonious set covering theory, set covering, set theory},
	doi = {10.1109/CAIA.1988.196115},
	author = {Sekar,S. and Reggia, James A.}
}
