Evolving Solutions to Graph Theory Problems
2023-05
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Evolving Solutions to Graph Theory Problems
Authors
Published Date
2023-05
Publisher
Type
Thesis or Dissertation
Abstract
Randomized search heuristics such as evolutionary algorithms are general-purposetechniques that have been shown to be effective at solving combinatorial optimiza-tion problems. In this thesis, we use both empirical and theoretical techniques toexamine the use of a simple evolutionary algorithm, the (1+1) EA, applied to com-binatorial optimization problems from graph theory. First, we investigate the evo-lutionary algorithm on problemsk-VertexCover,k-FeedbackVertexSet, andk-OddCycleTransversal, and present Fixed-Parameter Tractable performanceguarantees for the (1+1) EA equipped with a tailored jump-and-repair operator. Wethen follow up with empirical results of the (1+1) EA applied to thek-VertexCoverproblem. Next we move on to investigate the (1+1) EA applied to graceful labeling.We present the first rigorous runtime analysis of an evolutionary algorithm findinggraceful labelings of graphs, and prove polynomial time upper bounds for paths, stars,and complete bipartite graphs with a constant sized partition. To supplement thetheoretical results, we also empirically compare the performance of the (1+1) EA tothat of a complete constraint solver.ii
Keywords
Description
University of Minnesota M.S. thesis. May 2023. Major: Computer Science. Advisor: Andrew Sutton. 1 computer file (PDF); vii, 84 pages.
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Branson, Luke. (2023). Evolving Solutions to Graph Theory Problems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/258562.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.