Steiner tree
Graphs.jl provides some functionalities related to Steiner Trees.
Index
Full docs
Graphs.filter_non_term_leaves!
— Methodfilter_non_term_leaves!(g, term_vert)
Remove edges of g
so that all non-isolated leaves of g
are in the set term_vert
Graphs.steiner_tree
— Functionsteiner_tree(g, term_vert, distmx=weights(g))
Return an approximately minimum steiner tree of connected, undirected graph g
with positive edge weights represented by distmx
using Approximate Steiner Tree. The minimum steiner tree problem involves finding a subset of edges in g
of minimum weight such that all the vertices in term_vert
are connected.
t = length(term_vert)
.
Performance
Runtime: O(t(tlog(t)+|E|log(|V| )) Memory: O(t|V|) Approximation Factor: 2-2/t