Seminar Event Detail


Combinatorics

Date:  Friday, February 07, 2014
Location:  3866 East Hall (4:10 PM to 5:00 PM)

Title:  On testing Hamiltonicity of graphs

Abstract:   Given a directed graph on n vertices, it is an NP-complete problem to determine whether the graph contains a Hamiltonian circuit, that is, a closed walk that visits every vertex exactly once. The problem remains NP-complete if we ask whether one can add at most 0.001n new edges to the graph so that the new graph contains a Hamiltonian circuit. It is also an NP-hard problem to find out if the graph contains at least (0.001)^n n! Hamiltonian circuits. For any epsilon>0, I present a polynomial time algorithm which tells apart a directed graph on n vertices with at least (epsilon)^n n! Hamiltonian circuits from a directed graph on n vertices which does not acquire a Hamiltonian circuit unless some new epsilon n edges are added to it. The algorithm is based on a simple concentration result for permanents of dense matrices.

Files:


Speaker:  Alexander Barvinok
Institution:  UM

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.