On semidefinite programming bounds for graph bandwidth

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].
Original languageEnglish
Pages (from-to)485-500
JournalOptimization Methods and Software
Volume28
Issue number3
Publication statusPublished - 2013

Fingerprint

Semidefinite Programming
Bandwidth
Graph in graph theory
Semidefinite Programming Relaxation
Semidefinite Relaxation
Quadratic Assignment Problem
Graph Partitioning
Programming
Lower bound
Vertex of a graph

Cite this

@article{8afd69ca5da34d3b93abe83389315e2e,
title = "On semidefinite programming bounds for graph bandwidth",
abstract = "In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].",
author = "{de Klerk}, E. and M. Nagy and R. Sotirov",
note = "Special Issue in Honour of Professor Kess Roos' 70th Birthday",
year = "2013",
language = "English",
volume = "28",
pages = "485--500",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",
number = "3",

}

On semidefinite programming bounds for graph bandwidth. / de Klerk, E.; Nagy, M.; Sotirov, R.

In: Optimization Methods and Software, Vol. 28, No. 3, 2013, p. 485-500.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - On semidefinite programming bounds for graph bandwidth

AU - de Klerk, E.

AU - Nagy, M.

AU - Sotirov, R.

N1 - Special Issue in Honour of Professor Kess Roos' 70th Birthday

PY - 2013

Y1 - 2013

N2 - In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].

AB - In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].

M3 - Article

VL - 28

SP - 485

EP - 500

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 3

ER -