Back to search

Rochester Institute of Technology

An Alternative Approach to Counting Minimum (s; t)-cuts in Planar Graphs

Abstract

dc:description.abstract

Finding 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 × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/9690

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Silva, Rachel E. An Alternative Approach to Counting Minimum (s; t)-cuts in Planar Graphs. Thesis thesis, https://repository.rit.edu/theses/9690