21. ICPP 1992: University of Michigan, An Arbor, Michigan, USA - Volume 3

Quentin F. Stout (Ed.): Proceedings of the 1992 International Conference on Parallel Processing, August 17-21, 1992, University of Michigan, An Arbor, Michigan, USA. Volume III: Algorithms & Applications. CRC Press, ISBN 0-8493-0783-X

Reconfiguration and Broadcast

Rong Lin: Reconfigurable Buses with Shift Switching - VLSI RADIX Sort. 2-9 BibTeX
Dharmavani Bhagavathi, Peter J. Looges, Stephan Olariu, James L. Schwing, Jingyuan Zhang: A Fast Selection Algorithm for Meshes with Multiple Broadcasting. 10-17 BibTeX
Jang-Ping Sheu, Ming-Yang Su: A Multicast Algorithm for Hypercube Multiprocessors. 18-22 BibTeX
Jie Wu: Fault-Tolerant Nonredundant Broadcasting in Hypercubes. 23-26 BibTeX

Communication Algorithms

Marie-Claude Heydemann, Jaroslav Opatrny, Dominique Sotteau: Embeddings of Hypercubes and Grids into de Bruijn Graphs. 28-37 BibTeX
Junlin Liu, Bruce M. McMillin: A Divide and Conquer Ring Embedding Scheme in Hypercubes with Efficient Recovery Ability. 38-45 BibTeX
Jehoshua Bruck, Robert Cypher, Ching-Tien Ho: Fault-Tolerant de Bruijn and Shuffle-Exchange Networks. 46-50 BibTeX
Emmanouel A. Varvarigos, Dimitri P. Bertsekas: Partial Multinode Broadcast Algorithms for D-Dimensional Meshes. 51-54 BibTeX
Ching-Tien Ho, M. T. Raghunath: Efficient Algorithm for Gray-to-Binary Permutation on Hypercubes. 55-59 BibTeX

Linear Algebra I

Heonchul Park, Viktor K. Prasanna: A Class of Optimal VLSI Architectures for Computing Discrete Fourier Transform. 61-68 BibTeX
Javed I. Khan, Woei Lin, David Y. Y. Yun: A Parallel Matrix Inversion Algorithm on Torus with Adaptive Pivoting. 69-72 BibTeX
Sam H. Noh, Soo-Mook Moon, Ashok K. Agrawala: The RPT Parallel Gaussian Elimination Algorithm. 73-76 BibTeX
Ted H. Szymanski: The Complexity of FFT and Related Butterfly Algorithms on Meshes and Hypermeshes. 77-81 BibTeX
Yi-ling F. Chiang: On the Use of Adaptive Chebychev Iteration in Eigenvalue Problems. 82-86 BibTeX

Linear Algebra II

Harold E. Conn, Louis J. Podrazik: Parallel Recurrence Solvers for Vector and SIMD Supercomputers. 88-95 BibTeX
Kumar N. Ganapathy, Benjamin W. Wah: Synthesizing Otimal Lower Dimensional Processor Arrays. 96-103 BibTeX
Chua-Huang Huang, John R. Johnson, Rodney W. Johnson: Generating Parallel Programs from Tensor Product Formulas: A Case Study of Strassen's Matrix Multiplication Algorithm. 104-108 BibTeX
A. J. Huang, Z. George Mou: Parallel Partition Expansion for the Solution of Arbitrary Recurrences. 109-113 BibTeX

Geometry

Viktor K. Prasanna, Anil S. Rao: Parallel Orientation of Polygonal Parts. 115-122 BibTeX
Chang-Sung Jeong, Sun-Mi Kim, Seung-Bong Baek: Parallel Computation of Congruent Regions on SIMD Machines. 123-126 BibTeX
Ju-wook Jang, Viktor K. Prasanna: Efficient Parallel Algorithms for Some Geometric Problems on Reconfigurable Mesh. 127-130 BibTeX
Chandrasekhar Narayanaswami, Wm. Randolph Franklin: Boolean Combinations of Polygons in Parallel. 131-135 BibTeX
Fenglien Lee, Si-Qing Zheng: Constructing Voronoi Diagram of a Point Set on Mesh of Trees. 136-140 BibTeX
Soo-Young Lee, Nasser G. Azari: Hybrid Task Decomposition for Particle-in-Cell Method on Message Passing Systems. 141-144 BibTeX

Graph Theory

Ming-Shing Yu, Cheng-Hsing Yang: An Optimal Parallel Algorithm for the Domatic Partition Problem on Interval Graphs. 146-152 BibTeX
Wen-Jing Hsu, Carl V. Page, Jen-Shiuh Liu: Computing Prefixes on a Large Family of Interconnection Topologies. 153-159 BibTeX
Ming-Shing Yu, Lin Yu Tseng, Jiunn-Horng Lin: Optimal Parallel Algorithms for Some Problems on Trees. 160-163 BibTeX
Calvin Ching-Yuen Chen, Sajal K. Das: Efficient Parallel Algorithms for Computing Articulation Points and Bridges of Interval Graphs. 164-167 BibTeX

Hard Problems

Soo-Young Lee, Kyung-Geun Lee: Asynchronous Communication of Multiple Markov Chains in Parallel Simulated Annealing. 169-176 BibTeX
Kyung-Geun Lee, Soo-Young Lee: Efficient Parallelization of Simulated Annealing Using Multiple Markov Chains: An Application to Graph Partitioning. 177-180 BibTeX
Darrell R. Ulm, Pearl Y. Wang: Solving a Two-Dimensional Knapsack Problem on SIMD Computers. 181-184 BibTeX
Ira Pramanick: Application of a Parallel Heuristic Framework to the Set Covering Problem. 185-189 BibTeX
Arthur Ieumwananonthachai, Benjamin W. Wah: Parallel Statistical Selection in Multiprocessors. 190-194 BibTeX

Routing

Marios D. Dikaiakos, Anne Rogers, Kenneth Steiglitz: Message Ordering in Multiprocessors with Synchronous Communication. 196-203 BibTeX
Robert Cypher, Luis Gravano: Adaptive, Deadlock-Free Packet Routing in Torus Networks with Minimal Storage. 204-211 BibTeX
Abhijit Sengupta, Charles D. Elfe: On Fault-Tolerant Routing in Interconnection Digraphs. 212-215 BibTeX
Xiaoxiong Zhong, Virginia Mary Lo: An Efficient Heuristic for Application-Specific Routing on Mesh Connected Multicomputers. 216-219 BibTeX

Scheduling

David Nassimi: Parallel Algorithms for PM2B-ASCEND Computations on a SIMD Hypercube Using Multiple Levels of Iteration-Grouping. 221-228 BibTeX
Ramakrishna Thurimella, Yaacov Yesha: A Scheduling Principle for Precedence Graphs with Communication Delay. 229-236 BibTeX
Harish Sethu, Meghanad D. Wagh: Design of Time-Optimal Hardware-Efficient Divide-and-Conquer Algorithms. 237-240 BibTeX
Sadun Anik, Wen-mei W. Hwu: Executing Nested Parallel Loops on Shared-Memory Multiprocessors. 241-244 BibTeX

Simulation

Moon-Jung Chung, Yunmo Chung: Performance Prediction Based on Gate to Processor Ratio. 246-253 BibTeX
Jiajen M. Lin, Santosh G. Abraham: Discrete Event Simulation on Shared Memory Multiprocessors Using Global Simulation Information. 254-261 BibTeX
Tomohiro Kudoh, Tetsuro Kimura, Hideharu Amano, Takuya Terasawa: A Parallel Logic Simulation Algorithm Based on Query. 262-266 BibTeX
A. Cruz, D. Sarma: An Improved Parallel Processing Fault Simulator Algorithm: PLAto. 267-270 BibTeX

Sorting

Vinay S. Pai, Alejandro A. Schäffer, Peter J. Varman: Markov Analysis of Multiple-Disk Prefetching for External Mergesort. 272-279 BibTeX
Jang-Ping Sheu, Yuh-Shyan Chen, Chih-Yung Chang: Fault-Tolerant Sorting Algorithm on Hypercube Multicomputers. 280-284 BibTeX
Yen-Chun Lin: Perfectly Overlapped Sorting on a Linear Array. 285-288 BibTeX
Zicheng Guo: Sorting on Array Processors with Pipelined Buses. 289-292 BibTeX
Masood Bolorforoush, Nastaran S. Coleman, Donna J. Quammen, Pearl Y. Wang: A Parallel Randomized Sorting Algorithm. 293-296 BibTeX
Narsingh Deo, Amit Jain, Muralidhar Medidi: Constructing Height-Balanced Trees in Parallel. 297-300 BibTeX

Miscellaneous Algorithms I

Jing-Fu Fu Jenq, Sartaj Sahni: Image Shrinking and Expanding on a Pyramid. 302-309 BibTeX
Venkataramana Kommu, Irith Pomeranz: Effect of Communication in a Parallel Genetic Algorithm. 310-317 BibTeX
Peter Wohl, Thomas W. Christopher: Designing Conceptual Clustering for Parallel Implementation. 318-325 BibTeX
Win-Tsung Lo, Shietung Peng: An Optimal Parallel Algorithm for a Core of a Tree. 326-329 BibTeX

Miscellaneous Algorithms II

Eliezer Dekel, Jie Hu, Wen Ouyang: An Efficient Parallel Algorithm for Finding Compact Sets. 331-337 BibTeX
Hsing-Lung Chen, Nian-Feng Tzeng: Quick Determination of Subcubes in a Faulty Hypercube. 338-345 BibTeX
Peter Adamson, Evan Tick: Parallel Algorithms for the Single-Source Shortest-Path Problem. 346-350 BibTeX
Yennun Huang, T. V. Lakshman, Dipak Ghosal: On the Availability of Parallel Protocol-Processing Systems. 351-354 BibTeX
Young Man Kim, Ten-Hwang Lai, Yu-Chee Tseng: Compacting Free Buddy Subcubes in a Hypercube. 355-358 BibTeX