On bounding the bandwidth of graphs with symmetry

We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more

GRASP with path relinking heuristics for the antibandwidth problem

This paper proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with N nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2, …, … Read more