| Problems of edge selection, in particular problems involving cuts in graphs, have played a central role in algorithm design and complexity. The minimum cut problem, in which the objective is to partition the vertices of a graph such that the weight of edges connecting the two sets is minimum, is intimately tied to the theory of network flows. This area of combinatorial optimization is important not only because it has a wide variety of applications, but also because it illustrates the innovation and evolution of algorithm design.; In the first part of this thesis, we model applications found in forest science, biology, and electrical engineering as problems involving cuts. We hope to show that having a facility with the tools of operations research can be useful to researchers in other disciplines. Conversely, the operations research practitioner can uncover interesting problems in other disciplines that are ripe for analysis and that spawn general concepts of interest beyond the application at hand.; The second part of the thesis focuses on problems from a particular class of selection problems, namely bottleneck problems, in which the cut cost is given by a maximum weight edge. We hope that by focusing on a particular class of problems certain general techniques will emerge, especially relating to the somewhat ad-hoc area of approximation algorithms, for tackling such problems.; Our approach is to establish complexity results and to provide as efficient algorithms as possible for the problems studied. However, many cut problems (such as maximum cut) belong to the class of NP-complete or NP-hard problems thought to be immune to efficient general purpose solutions. In such cases, we attempt to develop efficient approximation algorithms whose solution is guaranteed to be within a certain factor of the optimal. Wherever possible, we provide "best-possible" algorithms in that guaranteeing a solution with better quality is itself NP-hard.; We hope that in some small way we can illustrate the ingenuity and richness of techniques inherent in algorithm design and analysis, be they polynomial or approximation algorithms, that makes this area of research at once challenging and frustrating but also stimulating and rewarding. |
