steiner trees in graphs

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

    We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more

    Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut

  • Francisco Barahona
  • Lazslo Ladanyi
    • Categories Branch and Cut Algorithms Tags , , ,

    We present a Branch-and-Cut algorithm where the Volume Algorithm is applied to the linear programming relaxations arising at each node of the search tree. This means we use fast approximate solutions to these linear programs instead of exact but slower solutions given by the traditionally used dual simplex method. Our claim is that such a … Read more