Questions tagged [spanning-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

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 ...
Daniele Cuomo's user avatar
3 votes
3 answers

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 ...
Optimization team's user avatar
0 votes
1 answer

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 ...
Eleonora's user avatar
3 votes
1 answer

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. ...
Daniele Cuomo's user avatar