New answers tagged minimum-spanning-tree
0
If we remove $e = (x,y)$ from $T_2$, then it breaks into two connected components, say $T_{2,x},T_{2,y}$. There is a unique path in $T_1$ from $x$ to $y$, which together with $e$ forms a fundamental cycle of $T_1$. The path starts at $T_{2,x}$ and ends at $T_{2,y}$, hence at some point it crosses between the two. Adding the corresponding edge to $T_2$ would ...
0
The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree.
Let's call $T$ the solution for the input graph $G$. Let's also call $T_i$ the solution for the problem $G_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I ...
4
As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).
Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS ...
3
Let's show first that such an edge might belong to a cycle, by considering the case of a square $ab,bc,cd,da$. We will show that $ab$ could belong to BFS trees starting at arbitrary vertices. This is clear if BFS is started from $a$ or from $b$. If BFS is started from $c$, it could enqueue $a,d$ in this order; dequeue $a$; then enqueue $b$. Similarly, if BFS ...
1
It turns out that there's a linear time algorithm, published in Carlson J., Eppstein D. (2006) The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems. In: Arge L., Freivalds R. (eds) Algorithm Theory – SWAT 2006. SWAT 2006. Lecture Notes in Computer Science, vol 4059. Springer, Berlin, Heidelberg.
The paper is paywalled, so I have ...
0
As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).
Top 50 recent answers are included
