Seminar Details:

LANS Informal Seminar
"A Continuous Multilevel Solver for the Vertex Separator Problem"

DATE: July 28, 2011

TIME: 10:30:00 - 11:30:00
SPEAKER: James Hungerford, MCS Summer Student and Ph.D. Student, Dept of Mathematics, Univeristy of Florida
LOCATION: Bldg 240 Conference Center 1416, Argonne National Laboratory

Description:
Given an undirected graph G, the vertex separator problem is to find the smallest number of nodes whose removal disconnects the graph into disjoint subsets A and B, where A and B are subject to size constraints. We will show how this problem can be formulated as a continuous quadratic program. We use the QP as a local processor in a multilevel scheme for solving large scale instances of the problem. Numerical results will be presented.


 

Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.