This dissertation presents accurate and scalable approaches to discover program dependences (relations) between various parts of the program and leveraging the dependences to improve development and maintenance tasks via program slicing (comprehension) and verification. The contents include new notions of control dependences that are suitable for modern program structures (e.g. non-terminating loops in reactive systems, exceptional control flow), a general algorithm to calculate data-based program dependences in concurrent programs, a parametric framework to describe program slicing algorithms, and the first stateful model checking algorithm that employs dynamic partial order reduction. The exposition employs illustrative examples, rigorous theoretical reasoning, and thorough experimental evaluation. The tools that embody the described techniques (and were used in the experimental evaluation) are freely available at http://indus.projects.cis.ksu.edu.