In this chapter, we describe several novel uses of combinatorial techniques that have found widespread use in realms outside traditional scientific computing. The “emerging” scientific disciplines of social and technological network analysis and computational molecular biology serve as the backdrop for our discussion. As illustrative case studies, we present two key problems in each of these areas. Most typical formulations of our chosen case studies are NP-hard optimization problems on graphs, and hence a great variety of new approximation algorithms and heuristics are being designed to solve them. We will provide a high-level overview of the problems, review some popular algorithmic strategies to solve them, and then focus our discussion on interesting combinatorial routines that these methods typically employ. Keeping with this book’s recurring theme of efficient “large-scale computing,” we highlight the state-of-the-art parallel approaches for solving these problems, and out-line challenges that may hinder scalable implementations on current parallel platforms.