Search

Spring 2011

Smith, Jacqueline

The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work...

Spring 2012

Enright, Jessica Anne

A set representation of a graph is an assignment of sets to vertices such that two vertices are adjacent if and only if their assigned sets have some specified relationship. We give several results related to set representations of graphs. We show that recognising the overlap and intersection...