\(E_i\) is a typo – should be \(F_i\). Also, use the acyclic shortest path algorithm to solve (Topological Ordering Algorithm).

Pairs of arcs changed into vertices for the lattice grid. Transform the problem into some type of shortest path. Find the solution of problem (using computer), then show that it's also optimal on the changed graph.

Optimality condition: \(0 \le c^{d}{i, j} = c{i, j} + d(i) - d(j)\)

Argue the transformation is correct.

label format (cost, flow, upper-bound).

• Decompose it into flow
• use theorem 3.8 to check whether the flow is an optimal solution to the minimum costs flow problem.

See page 63 for more information about potential functions and amortize complexity.

• The 3 operations happen in no particular order.
• The Big O notation indicates the number of time of an operations related to parameter m, n.
• It's is given that the potential function is bounded in such a way. It's saying that the operations are carried out for this and that way such that the potential function has this given bound on it.

Why in part (b), it says "that a (connected) graph". What is the significance of this particular condition here?

Because one example of an disconnected graph is 2 discrete cycle, which could both have odd length, and yet the graph is bipartitle

This assumption is not useful for part (a) of the proof.

Think back to the even cycle problem from 2.21 when judging this problem.

I think all of them are true.

For something that is very useful, please vists here, the wiki section with the definitions for everything.

Justify your answers with a proof or a counterexample.

For just Fig. 4.15(b).

Draw the network at each stage with the distance update(s) identified, the permanently labeled node(s), the node chosen to be permanently labeled, and the current tree.

See page 197 about the \(p_n(x^3)\).

Exercises to do: A, B, C