On bounding the bandwidth of graphs with symmetry

Research output: Contribution to journalArticleScientificpeer-review

210 Downloads (Pure)

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

Fingerprint

Bandwidth
Symmetry
Graph
Lower bounds

Keywords

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

Cite this

@article{180849f1e7d344d9842454a7605d4ee1,
title = "On bounding the bandwidth of graphs with symmetry",
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 weexploit 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.",
keywords = "bandwidth, minimum cut, semidefinite programming, Hamming graphs, Johnson graphs, Kneser graphs",
author = "{van Dam}, E.R. and R. Sotirov",
year = "2015",
doi = "10.1287/ijoc.2014.0611",
language = "English",
volume = "27",
pages = "75--88",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

On bounding the bandwidth of graphs with symmetry. / van Dam, E.R.; Sotirov, R.

In: INFORMS Journal on Computing, Vol. 27, No. 1, 2015, p. 75-88.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - On bounding the bandwidth of graphs with symmetry

AU - van Dam, E.R.

AU - Sotirov, R.

PY - 2015

Y1 - 2015

N2 - 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 weexploit 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.

AB - 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 weexploit 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.

KW - bandwidth

KW - minimum cut

KW - semidefinite programming

KW - Hamming graphs

KW - Johnson graphs

KW - Kneser graphs

U2 - 10.1287/ijoc.2014.0611

DO - 10.1287/ijoc.2014.0611

M3 - Article

VL - 27

SP - 75

EP - 88

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 1

ER -