{{ message }}

Instantly share code, notes, and snippets.

# pervognsen/graph_separators.txt

Last active Jan 10, 2021
 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.