Combinatorial Scientic Computing: The Enabling Power of Discrete Algorithms in Computational Science

Abstract. Combinatorial algorithms have long played a crucial, albeit under-recognized role in scientic computing. This impact ranges well beyond the familiar applications of graph algorithms in sparse matri-ces to include mesh generation, optimization, computational biology and chemistry, data analysis and parallelization. Trends in science and in computing suggest strongly that the importance of discrete algorithms in computational science will continue to grow. This paper reviews some of these many past successes and highlights emerging areas of promise and opportunity.