TITLE:

MAXIMUM CUT PROBLEM AND SPECTRUM OF A GRAPH (No. 104)

DATE:

Friday, February 17th, 2006

TIME:

3:30 PM

LOCATION:

GMCS 214

SPEAKER:

Dragan Stevanovic, Faculty of Sciences and Mathematics, Univerzitet u Nieu, Serbia, Yugoslavia

ABSTRACT:

In the first part of the talk, I will give a short overview of two of my papers dealing with theory of graph spectra: one on bounding the largest eigenvalue of nonregular graphs and the other on automatic generation of upper bounds for the largest Laplacian eigenvalue of graphs.

In the second part of the talk, I will present my latest results
dealing with applications of graph spectra: Inspired by the property of an eigenvector x corresponding to the least eigenvalue of an adjacency matrix of a bipartite graph, I propose a simple heuristic to produce a cut in an arbitrary graph $G=(V,E)$ by placing vertices with nonnegative x-component in one part and those with negative x-component in other part of the cut. While at the moment I know of no approximation guarantee to this heuristic, I will give some
theoretical support to its performance and provide results of extensive testing on DIMACS benchmark graphs.

Further, I will relate this heuristic to earlier work of Delorme and Poljak [DP1,DP2,DP3] on an eigenvalue upper bound on the size of the maximum cut and provide some extensions to their results.

References:

[DP1] C.Delorme, S.Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Program. 62 (1993), No.3(A), 557-574.

[DP2] C. Delorme, S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Math. 111 (1993), No.1-3, 145-156.

[DP3] C. Delorme, S. Poljak, Combinatorial properties and the complexity of a max-cut approximation, Eur. J. Comb. 14 (1993), No.4, 313-333.

HOST:

Jose Castillo

DOWNLOAD: