Maximum bandwidth path 0928
Given a weighted graph and 2 vertices s and t, find an s-t path of the largest bandwidth.
Def: Path bandwidth is the smallest edge bandwidth along the path.
Idea is to expand, pick shortest (max bandwidth) path. It’s a greedy method and guaranteed to find optimal with all positive edges.
Dijkstra Max Bandwidth
status: in-tree, fringe, unseen
Algorithm Dijkstra(G, s, t)
- FOR EACH v DO status[v] = unseen
- status[s] = in-tree
- FOR EACH [s, v] DO
status[v] = fringe
dad[v] = s
bw[v] = weight[s, v]; (INSERT(F,v) if using heap)
- WHILE status[t] in-tree DO
4.1. pick a fringe v with the largest bw[v] (v = POP(F), TOP then DELETE)
4.2. status[v] = in-tree
FOR EACH edge [v, w] DO
4.3. IF status[w] = unseen THEN
status[w] = fringe; dad[w] = v; bw[w] = MIN(bw[v], weight[v, w]) (INSERT(F, w))
4.4. ELSE IF status[w] = fringe and bw[w] < MIN(bw[v], weight[v, w]) THEN
dad[w] = v; bw[w] = MIN(bw[v], weight[v, w]) (DELETE old then INSERT new)
- output dad
Claim: This algorithm is correct.
Assume a better path exists. Any edges on this path is better than the smallest edge of the found path. When we try to pick this smallest edge from the fringe, we actually cannot get it. Instead, we will pick the edge on the better path. Therefore, we cannot find the found path. The assumption is invalid. This algorithm is correct.
The time complexity of this algorithm is . is number of nodes. is number of edges. It can actually reduced to . Because for all connected graph, cannot be smaller than . is for initialization. For partially connected graph, we won’t touch isolated nodes. So it still holds.
- Step 1 takes
- Step 2 takes
- Step 3:
- Step 4 WHILE loop will be executed at most times. Total time is .
- 4.1 takes .
- 4.2 is
- The FOR loop in step 4 will be executed times if directed; if undirected. Total time is .
- 4.3 takes
- 4.4 is
In order to use heap as the data structure, it must support DELETE action. We need an extra array to record the positions of the heap elements. Delete that element, then move the last element into that position and update position to keep the heap ordered. So it can be done in .
- adjacent matrix: If nodes, the size is .
- very sparse matrix
- for each edge
- adjacent list: A length list. Every element v stores a linked list [w1, w2,…] with weights, which are actually edges (v, w1), (v, w2),…
- In the worst case, still for each edge.
Max spanning tree 1004
is a graph, is a spanning tree for . If meets the following requirements:
- is a subgraph of .
- is a tree.
- contains all vertices of
Max spanning tree is a spanning tree whose sum of edge’s weight is the maximum.
Sort the edges of in non-increasing order: (if “no-decreasing” than for min spanning tree)
FOR = 1 to
IF does not make a cycle (, if do not belong to the same group of ) THEN
- Sorting the edges takes time of .
- The for loop takes time where runs times and each takes to check if the endpoints of the new edge belong to the same group of . We can use 2-3 tree to do it. trace from two endpoints to their roots; then check if the same root.
Since , . Therefore, the overall time is .
It is a tree
Three elements for a tree: graph, all connected, no cycle. It is apparently a graph. In terms of the Kruskal algorithm, it cannot include cycles. How to prove it is connected?
Proof by contradiction:
Assume pieces and are not connected, but there must be edge connecting and , and must be considered in this algorithm. Since it will not lead to a cycle, it will be added. So, and must be connected.
It is a max spanning tree
Claim: At any point, is a part of a max .
Proof by mathematical induction:
- By induction on this number times of for loop in Kruskal algorithm.
- The claim holds for .
- For , assume the claim holds for , The max ST is .
- For the case . Assume after executions of for loop,
- If the edge makes a cycle, we don’t add it, the claim holds.
- If we then add an edge, which is part of . The claim holds.
- Else, we add an edge which is not a part of . So, at a time point after , a edge which belongs to the will not be selected to avoid to form a cycle. Since this edge is after the in the , . So, what we get finally is a spanning tree with the sum of weights not smaller than the . According to the definition of max , the spanning tree is still a max spanning tree. Therefore, the claim holds at .
Maximum bandwidth path with MST 1010
Given a weighted graph and vertices and , find on path of the max bandwidth. if the graph is undirected, how to find it?
- construct a max spanning tree for
- find the path on
- return this path
Theorem 1: If is the the max contains the path, is a max bandwidth path in the graph .
- Assume a path is the max bandwidth path
- Pick any edge in that is not in .
- and some of form a cycle . (Since a max contains all vertices, so there must be a cycle)
- Claim the bandwidth of is not larger than any other edges in the cycle. Otherwise, will be a part of the max spanning tree (thinner edge will be removed). will not be a max .
- With this claim, we replace the edge by the edges in that forms a cycle with . The result is still a max-bandwidth path from that has fewer edges not in (Compared to ). Repeat this process, you will get max-bandwidth path that is entirely in .
Compared with Dijkstra algorithm
- It takes time only , with MST constructed.
- Do DFS with the adjacent list
- If including MST construction, MST is generally 4 times faster than Dijkstra
- Dijkstra is single-source. MST can trace from any source.
Max bandwidth path divide and conquer 1012
Remove the smaller half of edges
IF and are in the same piece
THEN recursively work on
Shrink each pieces into a single vertex in the original graph . Connect two pieces using the possible largest edge in the smaller half(How?) crossing them. Get the new graph be .
Recursively work on
smaller half finding
To find the smaller half, there is a algorithm.
k-th smallest finding
Do it directly when ; RETURN
- partition into groups of 5 (a group with 5 elements)
- FOR EACH group, find the group medians
- let the set of group medians be , It contains
- Recursive call on to find the median of
- split by into and
THEN recursively process and
ELSE recursively process and
Assume The algorithm takes .
- Step 1 takes
- Step 2 takes . For each group, 9 comparisons at most.
- Step 3 is trivial
- Step 4 takes
- Step 5 is
- Step 6 is
- and satisfy
Therefore, we have:
The guess is valid. So