Return to Colloquia & Seminar listing

### Traveling Salesman Path Perfect Graphs

**Algebra & Discrete Mathematics**

Speaker: | Fumei Lam, MIT |

Location: | 593 Kerr |

Start time: | Fri, Apr 16 2004, 4:10PM |

Given a graph G with edge costs and two vertices s and t, the traveling salesman path problem is that of finding a minimum-cost path beginning at s and ending at t that visits every vertex of G at least once. In this talk, we consider the polytope corresponding to a linear programming relaxation for this problem and characterize the set of graphs for which the vertices of this polytope are integral. (Joint work with Alantha Newman)