Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    The Minimum Labeling Spanning Tree Problem and Some Variants

    Thumbnail
    View/Open
    umi-umd-2758.pdf (653.5Kb)
    No. of downloads: 1525

    Date
    2005-08-05
    Author
    Xiong, Yupei
    Advisor
    Golden, Bruce L
    Metadata
    Show full item record
    Abstract
    The focus of my dissertation research involves combinatorial optimization. This is a key area in operations research and computer science. It includes lots of problems that have a wide variety of real-world applications. In addition, most of these problems are inherently difficult to solve. My specific disseration topic is the minimum labeling spanning tree (MLST) problem and some variants, including the label-constrained minimum spanning tree (LC-MST) problem and the colorful travaling salesman problem (CTSP). All of the three problems are NP-hard. The MLST problem tries to find a spanning tree of a graph with the smallest number of labels. The LC-MST problem tries to find the minimum-cost spanning tree of a graph with no more than K labels. The CTSP tries to find a hamiltonian cycle of a graph with the smallest number of labels. For each of the problems, we use both heuristic and genetic algorithms to solve them. From the computational results, the genetic algorithm can always obtain a better tradeoff between the solution quality and the running time. My disseration research shows that the genetic algorithm can be successfully applied to solve many NP-hard problems.
    URI
    http://hdl.handle.net/1903/2965
    Collections
    • Computer Science Theses and Dissertations
    • Mathematics Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility