# Tag Info

5

Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot to move from one position to the other. The edge lengths can be computed using the A* algorithm or any other pathfinding algorithm. Now I think you want a ...

4

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows: MST-PRIM(G,w,r) 1 for each u ∈ G.V 2 u.key = ∞ 3 u.π = NIL 4 r.key = 0 5 Q = G.V 6 while Q ≠ ∅ 7 u = EXTRACT-MIN(Q) 8 for each v ∈ G.Adj[u] 9 if v ∈ Q and w(u,v) < v.key 10 v.π = u 11 v.key = w(u,v) The loop in line 6 will ...

4

As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$. For the sake of simplicity, let's assume that $T$ is the unique MST. (This is not required, but it is easier to reason about correctness in this case.) Now think about what would happen if we ran Prim's on the full graph after ...

3

DECREASE-KEY is called at most $2|E|$ times: it is called at most twice per edge (i.e., for each edge $(u,v)$, we call DECREASE-KEY on $v$ when $u$ leaves the queue, and DECREASE-KEY on $u$ when $v$ leaves the queue). DECREASE-KEY costs $O(\log |V|)$ time per call to DECREASE-KEY. Therefore, the total cost from all of the DECREASE-KEYs is $O(|E| \log |V|)$,...

3

Question 1: However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$. You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$. All the vertices are already in $Q$ at ...

2

The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$ The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$

2

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is: Grow the tree, adding nodes one by one. On each step, select the minimum weight edge leading to a new node. You realise that whatever is the starting node, you have at least 2 choices....

2

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$. Let $(T, uv)$ be an optimal solution to the problem you describe, having ...

1

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights, with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe. At end of the ...

1

No. Here is a proof. Suppose $G$ is a weighted undirected graph such that for every cut of the graph, there is not a unique lightest edge crossing the cut. Let $M$ be a (or "the" in case it is unique) minimum spanning tree of $G$. Let $v$ be a leaf node of $M$. Consider the cut $\{\{v\},V\setminus \{v\}\}$ of $G$. Since $M$ is spanning, it contains an ...

1

I found this answer in a book: Consider a graph with 3 vertices a,b,c and weights w(a,b) = w(a,c) = 1 and w(b,c) = 2. The graph has a unique minimal spanning tree (containing edges (a,b) and (a,c)), however cut ({a}, {b,c}) doesn’t have a unique light edge crossing the cut. I hope it helps!

1

Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here. Your second solution: $v_0,v_1,v_3,v_2,v_7,v_8,v_6,v_4,v_5$ is incorrect. After adding $v_0,v_1,v_3,v_2$ you add $v_7$. But the minimum distance between $v_7$ and any existing ...

1

Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant. We will explicitly let $k=|F|$ be a constant. This constantness is indicated by "in such a case we can sort the edges in linear time.". It is then superfluous to "...

1

Note: This answer was written for a related problem where the goal is to minimize total distance travelled rather than elapsed time. This looks a lot like a minimum spanning tree problem (as your tags indicate). If we can compute a minimum spanning binary tree, then you could do the following (note that computing such a tree might take a while). Construct ...

1

The running time depends on how you implement the queue data structure. Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are much faster, if you're given the knowledge that every edge has weight either 1 or 2?

Only top voted, non community-wiki answers of a minimum length are eligible