Recognition Algorithms for 2-Tree Probe Interval Graphs

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