Lower and upper bounds for the spanning tree with minimum branch vertices.
Francesco CarrabsRaffaele CerulliManlio GaudiosoMonica GentiliPublished in: Comput. Optim. Appl. (2013)
Keyphrases
- spanning tree
- lower and upper bounds
- minimum weight
- undirected graph
- edge disjoint
- lower bound
- weighted graph
- minimum cost
- upper bound
- edge weights
- minimum spanning tree
- upper and lower bounds
- minimum total cost
- minimum spanning trees
- lagrangian relaxation
- np hard
- valid inequalities
- branch and bound algorithm
- approximation algorithms
- lagrangian dual
- worst case
- optimal solution