Mathematics Colloquia and Seminars

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)