Show simple item record

The Minimum Labeling Spanning Tree Problem and Some Variants

dc.contributor.advisorGolden, Bruce Len_US
dc.contributor.authorXiong, Yupeien_US
dc.date.accessioned2005-10-11T10:40:30Z
dc.date.available2005-10-11T10:40:30Z
dc.date.issued2005-08-05en_US
dc.identifier.urihttp://hdl.handle.net/1903/2965
dc.description.abstractThe 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.en_US
dc.format.extent669192 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleThe Minimum Labeling Spanning Tree Problem and Some Variantsen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentApplied Mathematics and Scientific Computationen_US
dc.subject.pqcontrolledMathematicsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record