Recognition Algorithms for 2-Tree Probe Interval Graphs

Item

Media: Full Text PDF

Title: Recognition Algorithms for 2-Tree Probe Interval Graphs
Author: David Avery
Faculty Sponsor: Mathew Nanity; Gavin Keulks
Date: 6/1/2015
Abstract: This thesis focuses on looking at a particular set of graphs and recognizing if a given graph has certain properties that would make it belong in this family, here called 2-tree Probe Interval Graphs. For these graphs, we create an algorithm to run on a coded script that recursively runs criteria through an input graph from its matrix representation to check the 2-path, and will output either a success that our graph is a 2-tree Probe Interval Graph, or failure if it is not. After the creation of this algorithm, a complexity analysis for the algorithm will be developed, as well as the implementation of di_erent search criteria to hopefully reduce the complexity by some polynomial factor. The recognition for our set of graphs follows to the conceptual idea that triangles are built upon each other in a fashion of adding one vertex and two edges to a previous triangle in the graph. Each new triangle is added to an existing triangle and recursively builds the graph where the new vertex neighbors strictly two vertices with an existing triangle, creating a recursively de_ned 2-path.
Type: Text; Honors Thesis
Department: Honors Program
Language: eng
Rights: Western Oregon University Library has determined, as of 06/01/2023, this item is in copyright, which is held by the author. Users may use the item in accordance with copyright limitations and exceptions, including fair use. For other uses, please ask permission from the author.; http://rightsstatements.org/vocab/InC/1.0/
Identifier: honors_theses/90