Questions tagged [spanning-trees]
The spanning-trees tag has no summary.
6 questions
5
votes
1
answer
273
views
MIP model for minimum spanning tree
In this post, Erwin Kalvelagen explores how the minimum spanning tree problem can me modeled with different MIPs. The models are based on Optimal Trees (Magnanti, Wolsey).
In the flow formulation II, ...
- 488
1
vote
1
answer
82
views
Does cutting a minimum spanning tree generate two minimum Steiner tree?
I am trying to understand whether this intuition is true or false.
Given a minimum spanning tree (MST) of an undirected positive graph $G=(V,E)$.
Consider a MST $T\subseteq G$. Removing any single ...
- 571
3
votes
3
answers
249
views
Directed trees and the order/score of each node in the tree
Suppose we have a directed tree as follows:
The information regarding the edges are also given to us as a list
like edge_info = [ (a,c) , (a,b) , (b,d) , (b,e) , (b,f) ]
I am trying to find a way to ...
- 1,420
0
votes
1
answer
69
views
Prove that a structure related to 1-tree is a matroid?
I am studying this chapter and I am stuck on page 262. In fact, I do not understand why the pair (E, $\tilde{\mathcal{S}}$) is a matroid where $\tilde{\mathcal{S}}$ is the set of all the subsets of ...
- 89
3
votes
1
answer
100
views
Steiner tree sub-optimal algorithm always finds the optimal solution. Why?
I am using the algorithm implemented by the library networkx to solve a Steiner minimal tree problem.
They claim their algorithm to give an approximated solution.
...
- 571
0
votes
2
answers
2k
views
Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree
I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie,
I need Miller-Tucker-Zemlin formulation ...
- 419