Optimization Online


On bounding the bandwidth of graphs with symmetry

Edwin van Dam (edwin.vandam***at***uvt.nl)
Renata Sotirov (r.sotirov***at***uvt.nl)

Abstract: We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the graph; one on each side of the cut. This fixing results in several smaller subproblems that need to be solved to obtain the new bound. In order to efficiently solve these subproblems we exploit symmetry in the data; that is, both symmetry in the min-cut problem and symmetry in the graphs. Our approach results in the best known lower bounds for the bandwidth of all graphs under consideration, i.e., Hamming graphs, 3-dimensional generalized Hamming graphs, Johnson graphs, and Kneser graphs, with up to 216 vertices.

Keywords: bandwidth, minimum cut, semide nite programming, Hamming graphs, Johnson graphs, Kneser graphs

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical report, Tilburg University, December 2012

Download: [PDF]

Entry Submitted: 12/02/2012
Entry Accepted: 12/02/2012
Entry Last Modified: 12/13/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society