On bounding the bandwidth of graphs with symmetry

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

Abstract

We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the min-cut problem. Our new semidefinite programming relaxation of the min-cut problem is obtained by strengthening the known semidefinite programming relaxation for the quadratic assignment problem (or for the graph partition problem) by fixing two vertices in the graph; one on each side of the cut. Fixing results in several smaller subproblems that need to be solved to obtain the new bound. 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. To obtain upper bounds for the bandwidth of graphs with symmetry, we develop a heuristic approach based on the well-known reverse Cuthill–McKee algorithm, and that improves significantly its performance on the tested graphs. Our approaches result in the best known lower and upper 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.
Original languageEnglish
Pages (from-to)75-88
JournalINFORMS Journal on Computing
Volume27
Issue number1
DOIs
Publication statusPublished - 2015

Keywords

  • bandwidth
  • minimum cut
  • semidefinite programming
  • Hamming graphs
  • Johnson graphs
  • Kneser graphs

Fingerprint Dive into the research topics of 'On bounding the bandwidth of graphs with symmetry'. Together they form a unique fingerprint.

Cite this