The Wandering Philosopher Problem

When
Start: 05/01/2013 - 4:15pm
End  : 05/01/2013 - 5:15pm

Category
Colloquium

Speaker
Tyler Seacrest (University of Western Montana)

Abstract

Suppose a wandering philosopher regularly visits every major city in an area, but she gets bored if she travels on the same path, and therefore never wants to use a road twice.  How many times can she make her tour of the cities before she needs to reuse a road?  In graph-theoretic terms, this problem is finding as many edge-disjoint Hamiltonian cycles as possible.

While this problem is several decades old, an approximate version has been very recently solved in three different ways by three different groups of researchers.  This one problem will allow us to discuss three very important tools in graph theory, tools that continue to pay big dividends today.

 

 

Where
Beckman B126, Harvey Mudd College

AttachmentSize
Seacrest.pdf105.22 KB