prize collecting steiner problem in graphs

STRONG LOWER BOUNDS FOR THE PRIZE COLLECTING STEINER PROBLEM IN GRAPHS

  • Abílio Lucena
  • Mauricio G.C. Resende
    • Categories Combinatorial Optimization, Network Optimization, Telecommunications Tags , , ,

    Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. … Read more