On the combinatorial lower bound for the extension complexity of the Spanning Tree polytope.

Kaveh Khoshkhah Dirk Oliver Theis

Published in: Oper. Res. Lett. (2018)

Keyphrases

spanning tree
lower bound
worst case
upper bound
minimum cost
edge disjoint
minimum weight
minimum spanning tree
computational complexity
minimum spanning trees
objective function
branch and bound algorithm
undirected graph
optimal solution
branch and bound
convex hull
stable set
sufficiently accurate