On semidefinite programming bounds for graph bandwidth

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

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 Dive into the research topics of 'On semidefinite programming bounds for graph bandwidth'. Together they form a unique fingerprint.

  • Cite this