Loading...
Please wait, while we are loading the content...
Similar Documents
An Alternative Approach to Counting Minimum (s; t)-cuts in Planar Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Silva, Rui J. C. |
| Copyright Year | 2017 |
| Abstract | An Alternative Approach to Counting Minimum (s, t)-cuts in Planar Graphs Rachel E. Silva, M.S. Rochester Institute of Technology, 2017 Supervisor: Dr. Ivona Bezáková 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://scholarworks.rit.edu/cgi/viewcontent.cgi?article=10835&context=theses&httpsredir=1&referer= |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
