|
|
Type of Document Master's Thesis Author Du, Ying Author's Email Address ydu1@nd.edu URN etd-04062004-144512 Title Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study Degree Master of Science in Computer Science and Engineering Department Computer Science and Engineering Advisory Committee
Advisor Name Title Dr. Danny Z. Chen Committee Member Dr. Jesus A. Izaguirre Committee Member Dr. Patrick J. Flynn Committee Member Keywords
- flow networks and flows
- segmenting images
Date of Defense 2003-12-10 Availability restricted Abstract The thesis presents the theory, implementation and experimental validation of a fastapproximation multicommodity flow algorithm and, as an important application of this
multicommodity flow algorithm, the first provably good approximation algorithm for the minimum normalized cut problem. The normalized cut problem has been applied to segment static images.
Our experimental results of the implementation of both algorithms show that the output quality of our approach compares favorably against some previous approximation multicommodity flow implementation and the eigenvalue/eigenvector based normalized cut implementation.
We also show the comparisons on the execution times and analyze the underlying reasons.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Du042004.pdf 245.34 Kb 00:01:08 00:00:35 00:00:30 00:00:15 00:00:01 indicates that a file or directory is accessible from the campus network only.