graph_separators.txt

A grid graph is a directed graph where the vertices are arranged in k rows each
containing k vertices, where k is a positive integer. Let v[i,j] denote the jth
vertex in the ith row. Let s = v[1,1]. A grid graph has the following vertices and edges:

V = {v[i,j] | 1 <= i <= k and 1 <= j <= k}

E = {(v[i,j], v[i,j+1]) | 1 <= i <= k and 1 <= j < k} union
    {(v[i,j], v[i,j-1]) | 1 <= i <= k and 1 < j <= k} union
    {(v[i,j], v[i+1,j]) | 1 <= i < k and 1 <= j <= k}

The below figure shows the grid graph for k = 5:

[See figure on last page of http://www.cs.au.dk/~gerth/dADS03/opgaver/s03.pdf. The
important thing to understand is that there are edges going in both directions horizontally
but vertically edges can only go upward.]

For the rest of this problem, we will assume all edges have non-negative weights.

Question A: Let n and m denote respectively the number of vertices and edges in a
grid graph. Express n and m as function of k.

Question B: What's the execution time of Dijkstra's algorithm to find the length of
the shortest paths from s = v[1,1] to all the other vertices in the grid graph, as a
function of k?

Question C: Describe an algorithm that finds the lengths of the shortest paths from
s = v[1,1] to all other vertices in a grid graph in time O(m). Prove the algorithm's
execution time and correctness.

A cylinder graph is a grid graph expanded with non-negatively weighted edges between
the leftmost and rightmost vertex in each row, i.e. E now also includes the edges
(v[i,1], v[i,k]) and (v[i,k], v[i,1]) for 1 <= i <= k.

Question D: Describe an algorithm that finds the lengths of the shortest paths from
s = v[1,1] to all other vertices in a cylinder graph in time O(m). Prove the algorithm's
execution time and correctness.