University of Notre Dame
Browse

File(s) under permanent embargo

Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study

thesis
posted on 2004-04-06, 00:00 authored by Ying Du
The thesis presents the theory, implementation and experimental validation of a fast approximation 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.

History

Date Created

2004-04-06

Date Modified

2018-10-08

Research Director(s)

Dr. Patrick J. Flynn

Committee Members

Dr. Patrick J. Flynn Dr. Danny Z. Chen Dr. Jesus A. Izaguirre

Degree

  • Master of Science in Computer Science and Engineering

Degree Level

  • Master's Thesis

Language

  • English

Alternate Identifier

etd-04062004-144512

Publisher

University of Notre Dame

Program Name

  • Computer Science and Engineering

Usage metrics

    Masters Theses

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC