-
June 29th, 2010, 08:46 PM
#1
MST + transitive closures + ... ?
Hi,
Given some positive-weighted directed graph, I'd like to find a cheapest set of edges s.t.
1. The set of vertices is a spanning tree, i.e. all vertices are present in the final graph
2. Every vertex is reachable from any other vertex through a directed path (transitive closure??)
3. Set of edges has the minimum cost
Essentially, I want the cheapest set of edges that allows me to go from every vertex to every other vertex through some directed path of any length.
Thanks for any help!
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|