Rochester Institute of Technology
An Alternative Approach to Counting Minimum (s; t)-cuts in Planar Graphs
Abstract
dc:description.abstractFinding and counting minimum cuts in graphs can be useful in image processing and segmentation and in networking systems such as computer or road networks. Researchers have previously developed polynomial-time algorithms to count minimum cuts in planar graphs which utilize the relationship between maximum network flows and minimum cuts. This thesis presents a polynomial-time algorithm to count the number of minimum (s,t)-cuts in a planar graph without first finding a maximum flow. The presented algorithm is dependent on the finding that (s,t)-cuts in a planar graph correlate to certain cycles found in the dual of that graph, which can be efficiently counted.
Degree
thesis:*- Name thesis:degree_name
- Computer Science (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science (GCCIS)
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Silva, Rachel E
- Contributors dc:contributor
-
- Ivona Bezakova
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.rit.edu/theses/9690