Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Publication
- Publication Type
Articles 1 - 5 of 5
Full-Text Articles in Theory and Algorithms
On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak
On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak
Theory and Applications of Graphs
The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …
Finding Optimal Cayley Map Embeddings Using Genetic Algorithms, Jacob Buckelew
Finding Optimal Cayley Map Embeddings Using Genetic Algorithms, Jacob Buckelew
Honors Program Theses
Genetic algorithms are a commonly used metaheuristic search method aimed at solving complex optimization problems in a variety of fields. These types of algorithms lend themselves to problems that can incorporate stochastic elements, which allows for a wider search across a search space. However, the nature of the genetic algorithm can often cause challenges regarding time-consumption. Although the genetic algorithm may be widely applicable to various domains, it is not guaranteed that the algorithm will outperform other traditional search methods in solving problems specific to particular domains. In this paper, we test the feasibility of genetic algorithms in solving a …
Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler
Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler
Graduate Student Theses, Dissertations, & Professional Papers
In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum …
Combinatorial Polynomial Hirsch Conjecture, Sam Miller
Combinatorial Polynomial Hirsch Conjecture, Sam Miller
HMC Senior Theses
The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the …
The Apprentices' Tower Of Hanoi, Cory Bh Ball
The Apprentices' Tower Of Hanoi, Cory Bh Ball
Electronic Theses and Dissertations
The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.