spanning trees

Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem

  • Frank de Meijer
  • Melanie Siebenhofer
  • Renata Sotirov
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Semi-definite Programming Tags , , , ,

    In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We give two formulations of the QMSTP as mixed-integer semidefinite programs exploiting the algebraic connectivity of a graph. Based on these formulations, we derive a doubly nonnegative relaxation for … Read more

    Network Reinforcement

  • Francisco Barahona
    • Categories Graphs and Matroids Tags

    We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them … Read more