Graphs are essential data structures in computational science and engineering, with algorithms based on them serving as computational kernels in data-intensive applications like social network analysis, computational biology, and scientific computing. To improve the performance of graph algorithms, high-performance computing techniques are vital for executing these algorithms on massively parallel architectures. However, the irregular memory access patterns and low arithmetic intensities of graph algorithms pose challenges for developing efficient parallel solutions. This thesis presents PAUL, a parallel auction-based weighted matching implementation designed to address the bipartite weighted graph matching problem on distributed memory clusters. It demonstrates that graph matching problems can be accelerated in various applications, including graph similarity in protein-protein interaction networks and matrix diagonalization in numerical linear algebra. Additionally, a dense subgraph problem is identified in parallel numerical linear algebra, whose resolution enhances the convergence and robustness of hybrid linear solvers. Three heuristics are developed to efficiently tackle this NP-hard combinatorial problem, with the most effective based on evolutionary algorithms. The effectiveness of these heuristics is showcased in the hybrid linear solver PSPIKE, applied to data-intensive challenges in arterial fluid dynamics and PDE-c
