Opened 9 years ago

Closed 9 years ago

#8403 closed enhancement (fixed)

Steiner Tree

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.5
Component: graph theory Keywords:
Cc: jason Merged in: sage-4.5.alpha1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (3)

trac_8403.patch (6.2 KB) - added by ncohen 9 years ago.
trac_8403-part2.patch (1.9 KB) - added by rlm 9 years ago.
trac_8403-rebased.patch (6.2 KB) - added by rlm 9 years ago.
apply before part 2

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by ncohen

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

comment:3 Changed 9 years ago by jason

  • Cc jason added

comment:4 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

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

comment:5 follow-up: Changed 9 years ago by ncohen

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..

comment:6 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is !

Nathann

Changed 9 years ago by ncohen

comment:7 in reply to: ↑ 5 Changed 9 years ago by rlm

Replying to ncohen:

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.

comment:8 follow-up: Changed 9 years ago by ncohen

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

comment:9 in reply to: ↑ 8 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller

Replying to ncohen:

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!

Changed 9 years ago by rlm

comment:10 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Thank you again ! :-)

Nathann

Changed 9 years ago by rlm

apply before part 2

comment:11 Changed 9 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.