Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Publication
- Publication Type
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
A Simplification Of Inclusion-Exclusion Via Minimal Complexes, Andrew J. Brandt
A Simplification Of Inclusion-Exclusion Via Minimal Complexes, Andrew J. Brandt
Summer Research
This poster discusses the discovery and use of previously unproved methods for solving counting problems using the fundamental ideas of the inclusion exclusion-principle and the Euler characteristic. While both methods use a weighted version of the Euler characteristic to determine the order of a union of finite sets, the first method can be used with contractible, planar graphs whereas the second method generalizes this idea to multi-dimensional complexes and their minimal complexes. These methods seem to be promising in their applications to subjects such as homology theory, Betti numbers, and abstract tubes.
Abstractions And Analyses Of Grid Games, Taylor Rowan Boone
Abstractions And Analyses Of Grid Games, Taylor Rowan Boone
Senior Projects Spring 2016
In this paper, we define various combinatorial games derived from the NQueens Puzzle and scrutinize them, particularly the Knights Game, using combinatorial game theory and graph theory. The major result of the paper is an original method for determining who wins the Knights Game merely from the board's dimensions. We also inspect the Knights Game's structural similarities to the Knight's Tour and the Bishops Game, and provide some historical background and real-world applications of the material.
Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.
Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.
CCE Theses and Dissertations
The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark …
Winning Strategies In The Board Game Nowhere To Go, Najee Kahil Mcfarland-Drye
Winning Strategies In The Board Game Nowhere To Go, Najee Kahil Mcfarland-Drye
Senior Projects Spring 2016
Nowhere To Go is a two player board game played on a graph. The players take turns placing blockers on edges, and moving from vertex to vertex using unblocked edges and unoccupied vertices. A player wins by ensuring their opponent is on a vertex with all blocked edges. This project goes over winning strategies for Player 1 for Nowhere To Go on the standard board and other potential boards.
Exploring Tournament Graphs And Their Win Sequences, Sadiki O. Lewis
Exploring Tournament Graphs And Their Win Sequences, Sadiki O. Lewis
Senior Projects Fall 2016
In this project we will be looking at tournaments on graphs and their win sequences. The main purpose for a tournament is to determine a winner amongst a group of competitors. Usually tournaments are played in an elimination style where the winner of a game advances and the loser is knocked out the tournament. For the purpose of this project I will be focusing on Round Robin Tournaments where all competitors get the opportunity to play against each other once. This style of tournaments gives us a more real life perspective of a fair tournament. We will model these Round …
Some Extremal And Structural Problems In Graph Theory, Taylor Mitchell Short
Some Extremal And Structural Problems In Graph Theory, Taylor Mitchell Short
Theses and Dissertations
This work considers three main topics. In Chapter 2, we deal with König-Egerváry graphs. We will give two new characterizations of König-Egerváry graphs as well as prove a related lower bound for the independence number of a graph. In Chapter 3, we study joint degree vectors (JDV). A problem arising from statistics is to determine the maximum number of non-zero elements of a JDV. We provide reasonable lower and upper bounds for this maximum number. Lastly, in Chapter 4 we study a problem in chemical graph theory. In particular, we characterize extremal cases for the number of maximal matchings in …