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