In the edge-disjoint paths problem, you are given a directed unweighted graph G=(V,E), two vertices n ÎV and v ÎV , and an integer K.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1  (Fill the blank) In the edge-disjoint paths problem, you are given a directed unweighted graph G=(V,E), two vertices n ÎV and v ÎV , and an integer K. The problem is to decide whether there are K paths from n to v whose edges do not overlap. Show how to solve this problem by transferring it into a max-flow problem.______________ The run-time complexity of this algorithm is O(________)?

2 (T/F) For a given weighted connected graph G=(V, E), we would like to find the longest simple path between any two vertices. We can solve this problem by negating the edge weights and running Johnson’s algorithm.

3 (T/F) Consider the all pairs shortest paths problem where there are also weights on the vertices, and the weight of a path is the sum of the weights on the edges and vertices on the path. Then, the following algorithm finds the weights of the shortest paths between all pairs in the graph:

APSP-WITH-WEIGHTED-VERTICES (G, w):

1 for (u, v) Î E

2          Set w’(u, v)=(w(u)+w(v))/2 +w(u, v)

3 Run Johnson’s algorithm on G, w’ to compute the distances d’ (u, v) for all u, vÎV

4 for u, v Î V

5    Set du, v = d’(u, v)+1/2(w(u)+w(v))

 

4 (Fill the blank) Given a weighted directed graph G = (V, E), where every edge in the graph has negative weight, can determining whether the graph contains a negative weight cycle be done in O(V+E) time? If Yes explain how. If No, explain why?

___________________________________________

 

5 (Fill the blank) Given a weighted graph G=(V, E, w), the radius r(a) of a vertex is the largest weight of any minimum-weight path from a to any other vertex, i.e. r(a)=max{d(a, b)| b ÎV }; and the graph radius R(G) of G is the smallest radius of any vertex, i.e. R(G)=min{r(a)| a ÎV}. Describe an O(|V|3) time algorithm to compute weights, but no negative weight cycle.

______________________________________

6 (Fill the blank) A Hamiltonian Path is a path in a directed graph that visits every vertex exactly once. Describe a linear time algorithm to determine whether a directed acyclic graph G=(V, E) contains a Hamiltonian path. (Hint: It might help to draw a DAG which contains a Hamiltonian path)_______________________

 

7 (Fill the blank with a value) Let S= {(x1, y1), … (xn, yn)} be a set of n points in the plane. You have been told that there is some k such that the points can be divided into k clusters with the following properties:

1 Each cluster has radius r.

2 The center of each cluster has distance at least 5r from the center of any other cluster.

We can use the following algorithm to compute the number of clusters and collect all the clusters:

Algorithm Initialize the number of clusters k º 0 and the set S’ º S. Choose a point P ÎS’ and compute the distance from p to every other point in S’. Remove p and all points within distance 2r from S’ and increment k. Repeat this procedure until S’ is empty at that point, return k and all the points removed in each iteration as a cluster. We can prove if the point p chosen in an iteration lies in a cluster with center c, then for any other point q in this cluster, d(p, q)£__×r by triangular inequality.

 

8 (Fill the 1st blank with a phrase and remaining blanks with values) continued from the previous question. We can prove is q’ is in another cluster with center c’. then

d(p, q’) = (d(c, p) + d(p, q’) +d(q’, c’)) - d(c, p) - d(q’, c’)

³ d(c, c’) – d(c, p) – d(q’, c’)               (This is due to __________)

³ ___×r - ____×r - ___×r = __×r.

 

9 (Fill the blanks) The edge connectivity is the minimum number K of edges that must be removed to disconnect the graph into two or more components. Given an undirected unweighted graph G=(V, E), design an algorithm that uses maximum flow algorithm to compute the edge connectivity and provide the runtime analysis for your algorithm. You may give your runtime in terms of T(n, m), the runtime of the best algorithm for computing maximum flow values on a graph of n nodes and m edges._____________________________________________

 

10 (T/F) If each operation on a data structure runs in O(1) amoritized time, then n consecutive operations run in O(n) time in the worst case. Answer True. Recall that inputs (that is , it doesn’t take into account what happens “on average”)

 

11 (Fill the blank with a value) Given an undirected graph G= (V, E) and two vertices s, t ÎV, a maximum s-t cut is a cut (S, T) satisfying the following conditions:

I (S, T) is a cut: S, T Ì V, SÇT = Æ, and SÈT = V.

II sÎS and tÎT.

III The number of edges (u, v) ÎE with uÎS and vÎV \ S is the maximum possible.

The MAXIMUM-s-t-CUT problem is to find a maximum cut for a given pair of vertices.

MAXIMUM-s-t-CUT is NP-hard. Analyze the following algorithm

MAX-CUT(G, s, t)

• S¬{s}
• T¬{t}
• For each vertex vÎV- {s, t}
• do
• a¬ the number of edges (u, v) with u Î
• b¬ the number of edges (v, w) with w Î
•          if a > b
• then
• T¬TÈ{v}
• else
• S¬SÈ{v}
• return (S, T) as the approximation for the Maximum-s-t-CUT of s and t.

Each time we add a new vertex v to the cut, compare the number of edges added into the edge cuts with the total number of edges connecting v to S and T. We can conclude the size of the s-t-cut produced must be at most __________ factor of the maximum-s-t-cut.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of