Alexandre Cunha

On the NP-Completeness of the Multi-Period Minimum Spanning Tree Problem

  • Rosklin Chagas
  • Alexandre Cunha
    • Categories Combinatorial Optimization, Scheduling, Telecommunications Tags ,

    In this note, we consider the Multi-period Minimum Spanning Tree Problem (MMST), a variant of the well known Minimum Spanning Tree Problem (MST), that consists in the fol- lowing. Given a connected and undirected graph G and a finite discrete time horizon, one has to schedule the moment in time edges are added to a … Read more

    A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

  • Alexandre Cunha
  • Abílio Lucena
    • Categories Branch and Cut Algorithms, Telecommunications Tags , , ,

    A new exact solution algorithm is proposed for the Degree-Constrained Minimum Spanning Tree Problem. The algorithm involves two combined phases. The first one contains a Lagrangian Relax-and-Cut procedure while the second implements a Branch-and-Cut algorithm. Both phases rely on a standard formulation for the problem, reinforced with Blossom Inequalities. An important feature of the proposed … Read more