Browsing by Author "Branson, Luke"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Antimagic Labelings for Trees of Order 3 to 25(2023-07-14) Branson, Luke; Sutton, Andrew M; amsutton@d.umn.edu; Sutton, Andrew; University of Minnesota Algorithmic Evolution LabThis dataset contains antimagic labelings of all trees of order 3 to 25 as described in the paper "Finding Antimagic Labelings of Trees by Evolutionary Search"Item Evolving Solutions to Graph Theory Problems(2023-05) Branson, LukeRandomized 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