Date of Award
2006
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Yuri Boykov
Abstract
Maximum flow algorithms must balance two competing factors in performance: flow should reach its destination via short paths, but finding short paths is expensive. Push-relabel algorithms compute these paths via an evolving map, called a labeling, over the vertices. The first push-relabel algorithms (Goldberg & Tarjan [32]), use three well-known relabeling operations: (local) relabel, global relabel, and gap relabel. We contribute a new push-relabel algorithm that uses more flexible relabeling operations. The three standard operations all become special cases of our new and more general relabeling operations. On sparse graphs, our algorithm is easy to parallelise and operates efficiently within limited memory. What makes our contribution of particular interest is that the original push-relabel algorithms still, to this day, have the most robust performance in practice [1, 16, 9. Our preliminary experiments suggest that we have opened a door to improving the state of the art for immense, sparse grid-graphs common in computer vision and biomedical imaging applications.
Recommended Citation
Delong, Andrew T., "A Scalable Max-Flow/Min-Cut Algorithm for Sparse Graphs" (2006). Digitized Theses. 4685.
https://ir.lib.uwo.ca/digitizedtheses/4685