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

### Dijkstra

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 EACHvDOstatus[v] = unseen- status[s] = in-tree
FOR EACH[s, v]DOstatus[v] = fringe

dad[v] = s

bw[v] = weight[s, v]; (INSERT(F,v) if using heap)WHILEstatus[t] in-treeDO4.1. pick a fringe v with the largest bw[v] (v = POP(F), TOP then DELETE)

4.2. status[v] = in-tree

FOR EACHedge [v, w]DO4.3.

IFstatus[w] = unseenTHENstatus[w] = fringe; dad[w] = v; bw[w] = MIN(bw[v], weight[v, w]) (INSERT(F, w))

4.4.

ELSE IFstatus[w] = fringe and bw[w] < MIN(bw[v], weight[v, w])THENdad[w] = v; bw[w] = MIN(bw[v], weight[v, w]) (DELETE old then INSERT new)

- output dad

#### Correctness

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.

#### Analysis

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

#### Heap

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 .

### Graph representation

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

### Kruskal Algorithm

Algorithm **Kruskal(G)**

Sort the edges of in non-increasing order: (if “no-decreasing” than for min spanning tree)

FOR= 1 to

IFdoes not make a cycle (, if do not belong to the same group of )THENDO

RETURN

#### Analysis

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

#### Correctness

##### 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?

Idea is:

- construct a max spanning tree for
- find the path on
- return this path

### Correctness

**Theorem 1**: If is the the max contains the path, is a max bandwidth path in the graph .

#### Proof

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

### Analysis

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

### Algorithm

**max-bandwidth path**

Remove the smaller half of edges

IFand are in the same piece

THENrecursively work on

ELSEShrink 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 EACHgroup, 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
IF

THENrecursively process and

ELSErecursively process and

##### Analysis

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:

Guess

The guess is valid. So

## Reference

This is my class note of CSCE 629 in Texas A&M taught by Dr. Jianer Chen. I also get help from Yun He’s note on MST part. Credit to them.