Back to Search
Start Over
On semidefinite programming bounds for graph bandwidth.
- Source :
-
Optimization Methods & Software . Jun2013, Vol. 28 Issue 3, p485-500. 16p. 7 Charts. - Publication Year :
- 2013
-
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]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10556788
- Volume :
- 28
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Optimization Methods & Software
- Publication Type :
- Academic Journal
- Accession number :
- 87666802
- Full Text :
- https://doi.org/10.1080/10556788.2012.709856