On semidefinite programming bounds for graph bandwidth

DOI10.1080/10556788.2012.709856zbMath1273.90151OpenAlexW2155986034MaRDI QIDQ5299908

Marianna. E.-Nagy, Renata Sotirov, Etienne de Klerk

Publication date: 24 June 2013

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2012.709856

zbMATH Keywords

semidefinite programmingquadratic assignment problemcyclic bandwidthgraph bandwidth

Mathematics Subject Classification ID

Semidefinite programming (90C22) Discrete location and assignment (90B80)

Related Items

Tabu search for the cyclic bandwidth problem, Lower bounds for the bandwidth problem, Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem

Uses Software

• GAP
• YALMIP

Cites Work

• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• Optimal labelling of a product of two paths
• The NP-completeness of the bandwidth minimization problem
• Semidefinite programming relaxations for the quadratic assignment problem
• Bandwidth of the complete \(k\)-ary tree
• Improved Bandwidth Approximation for Trees and Chordal Graphs
• Relaxations of Combinatorial Problems Via Association Schemes
• SDP Relaxations for Some Combinatorial Optimization Problems
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• A spectral approach to bandwidth and separator problems in graphs
• A Copositive Programming Approach to Graph Partitioning
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Optimal numberings and isoperimetric problems on graphs
• Characterization of graphs with equal bandwidth and cyclic bandwidth