Opened 10 years ago
Closed 10 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)
Change History (14)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
- Cc jason added
comment:4 Changed 10 years ago by
- 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: ↓ 7 Changed 10 years ago by
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 10 years ago by
- Status changed from needs_work to needs_review
Here it is !
Nathann
Changed 10 years ago by
comment:7 in reply to: ↑ 5 Changed 10 years ago by
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: ↓ 9 Changed 10 years ago by
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 10 years ago by
- 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 10 years ago by
comment:10 Changed 10 years ago by
- Status changed from needs_review to positive_review
Thank you again ! :-)
Nathann
comment:11 Changed 10 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
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