bandwidth

On bounding the bandwidth of graphs with symmetry

  • Renata Sotirov
  • Edwin van Dam
    • Categories Semi-definite Programming Tags , , , , ,

    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

  • Abraham Duarte
  • Mauricio G.C. Resende
  • Ricardo M.A. Silva
  • Rafael Martí
    • Categories 0-1 Programming, Meta Heuristics, Stochastic Approaches Tags , , , , ,

    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