Steiner Tree

[nathanncohen]

Here is a patch containing the function Graph.steiner_tree.

It consists in finding in a graph, given a set S of vertices, a tree in G of minimum weight/cardinality containing the vertices from S.

Everything is explained in the docstrings anyway :-)

Nathann

CC: @jasongrout

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.5.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/8403

[nathanncohen]

comment:2

For an explanation of the Linear Program used to solve this problem, see the LP chapter from : http://code.google.com/p/graph-theory-algorithms-book/

Nathann

[rlmill]

comment:4

I don't think that, as you claim, minimum spanning trees can be computed in linear time.

[nathanncohen]

comment:5

And you are right. I was thinking about spanning trees, as I usually do not care about weights, but min spanning trees require a bit longer. nlog(n) is enough , even if better can be achieved, by first sorting the edges according to their weights, then greedily building a spanning tree..

[nathanncohen]

comment:6

Here it is !

Nathann

[rlmill]

comment:7

Attachment: trac_8403.patch.gz

Replying to @nathanncohen:

And you are right. I was thinking about spanning trees, as I usually do not care about weights...

I don't think spanning tree is linear: the standard method is a BFS/DFS, which is still worst case quadratic. I know this is no longer relevant here, but I want to make sure I have this right. If you do know of a linear time spanning tree algorithm, I'm curious about it.

[nathanncohen]

comment:8

That's what I call linear -- not according to the the number of vertices, but according to the size of the input : n+m :-)

Nathann

[rlmill]

Author: Nathann Cohen

[rlmill]

Reviewer: Robert Miller

[rlmill]

comment:9

Replying to @nathanncohen:

That's what I call linear -- not according to the the number of vertices, but according to the size of the input : n+m :-)

Aha, thanks for clarifying. If you approve of my part2, set the ticket to positive-- all looks good to me!

[nathanncohen]

comment:10

Attachment: trac_8403-part2.patch.gz

Thank you again ! :-)

Nathann

[rlmill]

apply before part 2

[rlmill]

comment:11

Attachment: trac_8403-rebased.patch.gz

[rlmill]

Merged: sage-4.5.alpha1