# Tag Info

Accepted

### Finding MST after adding a new vertex

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. ...
• 176

### Minimum path - robot motion problem combined with freeze tag problem

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 ...
• 162k

### Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows: ...
• 141
Accepted

### MST with weights in {1, 2, 3, 4, 5}

Let $G_0$ be your input graph, label each edge $(u,v)$ with $(u,v)$ itself. Repeat the following for all values of $i$ from $1$ to $5$: Compute a spanning forest $F_i$ of the subgraph of $G_{i-1}$ ...
• 29.5k
Accepted

### Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

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$ ...
• 162k
Accepted

### Time complexity of Prim's algorithm

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 ...
• 1,428

### MST for a finite number of weights

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 ...
• 39.1k
Accepted

### Minimum spanning tree such that one edge can be minimised

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 ...
• 5,479
Accepted

### MST: Is there such an example of a graph with unique mst and not unique light edge?

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 ...
• 39.1k

### MST: Is there such an example of a graph with unique mst and not unique light edge?

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)...

### MST: Is there such an example of a graph with unique mst and not unique light edge?

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: ...
• 1,788
Accepted

### Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

When we want to design an algorithm, we mainly consider how our data is organized. When we model a problem with graph for example, the things we could do are restricted to this specified model. For ...
Accepted

### Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

Let $n=|V|$ and $m=|E|$. Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning ...
• 29.5k
Accepted

### Find MST with bounded edge weight in O(|V|+|E|)

You should use Prim's algorithm instead of Kruskal's algorithm. Given a weighted undirected graph $G = (V, E, f)$ with $f(E) \subseteq \{1, 2, 3\}$ as an adjacency lists array, the following should ...
• 15.8k
1 vote

### Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

One way to see the similarities between BFS and DFS is to consider them as the same algorithm (or perhaps some sort of "meta algorithm"), but using a different underlying data-structure: BFS ...
• 8,303
1 vote
Accepted

### Minimum Spanning Tree with one particular edge minimised(continued)

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 ...
• 39.1k
1 vote
Accepted

### Minimum spanning tree - Prim's algorithm

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 ...
• 453
1 vote

### Minimum path - robot motion problem combined with freeze tag problem

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 ...
• 131
1 vote
Accepted

### Prim's algorithm on graph with weights of only $1$ and $2$ on each edge

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 ...
• 162k
1 vote

### Finding MST after adding a new vertex

(This is a copy of the answer to the same question on the general StackOverflow) There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is ...

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