Skip to main content
3 of 11
Formatting
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

Given a digraph and a root, find a tree that minimizes the sum of edges

I want to find a mathematical formulation to use in GLPK. Given a directed graph and a root, I need to find a tree that minimizes the value of the edges in that graph. Note that we DON'T need to include all vertices.

Example

In that example the root is A and the tree that minimizes the cost of edges is $A,C,E,D$ with cost $-4$. In other words I want to find a tree with minimum value, the number of nodes doesn't matter at all.

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.

Any help with related problems? I can't find any material or papers...