Lawrence Berkeley National Laboratory

Combinatorial algorithms have long played apivotal enabling role in many applications of parallel computing. \index Graph algorithms in particular arise in load balancing, scheduling, mapping and many other aspects of the parallelization of \index irregular applications. These are still active research areas, mostly due toevolving computational techniques and rapidly changing computational platforms. But the relationship between parallel computing and discrete algorithms is much richer than the mere use of \index graph algorithms to support the parallelization of traditional scientific computations. Important, emerging areas of science are fundamentally discrete, and they are increasingly reliant on the power of parallel computing. Examples include \index computational biology, \index scientific datamining, and \index network analysis. These applications are changing the relationship between \index discrete algorithms and parallel computing. In addition to their traditional role as enablers of high performance, \index combinatorial algorithms are now customers for parallel computing. New parallelization techniques for combinatorial algorithms need to be developed to support these nontraditional scientific approaches. This chapter will describe some of the many areas of intersection between discrete algorithms and parallel scientific computing. Due to space limitations, this chapter is not a comprehensive survey, but rather an introduction to a diverse set of techniques and applications with a particular emphasis on work presented at the Eleventh SIAM Conference on Parallel Processing for Scientific Computing. Some topics highly relevant to this chapter (e.g., \load balancing) are addressed elsewhere in this book, and so we will not discuss them here.