StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
16622864
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-05-18T09:46:51.043
FavoriteCount
0
LastActivityDate
2013-05-18T09:46:51.043
LastEditDate
LastEditorUserId
0
OwnerUserId
774674
ParentId
16458017
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
Given a weighted undirected graph G(V,E), and a set S subset of V find the Minimum-Cost tree that spans the nodes in S. This problem is known in the literature as the Steiner tree problem. The problem is NP-complete, which means that there is no known polynomial algorithm that will find the exact solution of the problem. However, there are algorithms that solve the Steiner problem in exponential time (O(2^N) or O(2^M)). The Naive or Shortest Paths algorithm. <pre><code>Find the Shortest path tree from one participant node to the rest of the graph. Prune the parts of the tree that do not lead to a participant. </code></pre> Complexity O(N^2), CR = O(M). The Greedy or Nearest Participant First algorithm. (Takahashi, Matsuyama 1980) Start from a participant. <pre><code>Find the participant that is closest to the current tree. Join the closest participant to the closest part of the tree. Repeat until you have connected all nodes. </code></pre> Complexity O(M N^2), CR = O(1), actually CR <= 2. The Kou, Markowsky and Berman algorithm (KMB 1981). <pre><code>1. Find the complete distance graph G' (G' has V' = S , and for each pair of nodes (u,v) in VxV there is an edge with weight equal to the weight of the min-cost path between these nodes p_(u,v) in G) 2. Find a minimum spanning tree T' in G' 3. Translate tree T' to the graph G: substitute every edge of T', which is an edge of G' with the corresponding path of G. Let us call T the result of the translation. 4. Remove any possible cycles from T. </code></pre> Complexity O(M N^2), CR = O(1), actually CR <= 2. 
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POShortest path while walking x unique nodes
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USAditya
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POShortest path while walking x unique nodes
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.