To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
The Third Annual DIMACS Implementation Challenge was formulated with the view to provide a forum for a concerted effort to study effective algorithms for combinatorial problems, and to investigate opportunities for massive speedups on parallel computers. The challenge included two problem areas for research study: (a) tree searching algorithms, used in game search and combinatorial optimization for example; and (b) algorithms for sparse graphs.
Participants at sites in the U.S. and Europe undertook projects during the period from November 1993 to October 1994. The Challenge workshop was held at DIMACS on October 17 and 18, 1994. Following the workshop, participants were encouraged to share test instances where possible, to rework their implementations in light of the feedback at the workshop, and to submit a final report for the proceedings. Nine papers were selected for this volume.
Approximately 50 researchers attended the workshop; there were 17 project presentations, 7 invited talks, and a panel discussion. The specific application problems presented at the workshop included connected components and shortest paths in graphs, geometric clustering and dominance, graph partitioning, N-body algorithms for astrophyiscs, branch-and-bound techniques, and massively parallel chess. The invited presentations focused on topics ranging from good experimental methodology (Guy Blelloch, David Johnson); the interplay between modeling, algorithm design, and implementation (David Culler); and specific applications such as factoring (Arjen Lenstra), traveling salesman (David Applegate), and mesh partitioning (Shanghua Teng, Zdenek Johann).
The expert assistance of the DIMACS staff in hosting and arranging the workshop is gratefully acknowledged. The NSF STC grant supported Pangfeng Liu as a DIMACS post-doctoral fellow to help coordinate the Challenge. Thanks to Pangfeng for his efforts, and also to the rest of the Challenge Steering Committee, which included David Culler (UC Berkeley), David Johnson (AT&T Labs), Lennart Johnsson (Univ. of Houston) and Charles Leiserson (MIT).
TABLE OF CONTENTS
Foreword ix Preface xi Connected components on distributed memory machines ARVIND KRISHNAMURTHY, STEVEN S. LUMETTA, DAVID E. CULLER, AND KATHERINE YELICK 1 Parallel implementation of algorithms for finding connected components in graphs TSAN-SHENG HSU, VIJAYA RAMACHANDRAN, AND NATHANIEL DEAN 23 Connected components algorithms for mesh-connected parallel computers STEVE GODDARD, SUBODH KUMAR, AND JAN F. PRINS 43 Implementing parallel shortest-paths algorithms MARIOS PAPAEFTHYMIOU AND JOSEPH RODRIGUE 59 Finding friends-of-friends clusters quickly BRENDAN MUMEY 69 A practical comparison of N-body algorithms GUY BLELLOCH AND GIRIJA NARLIKAR 81 Parallel algorithms for geometric dominance problems JAN PETERSSON 97 The *Socrates massively parallel chess program CHRISTOPHER F. JOERG AND BRADLEY C. KUSZMAUL 117 Concurrent data structures and load balancing strategies for parallel branch-and-bound/A* algorithms V.-D. CUNG, S. DOWAJi, B. LE CUN, T. MAUTOR, AND C. ROUCAIROL 141