2.0p Grid outerconnect 1 An n x n grid is an undirected graph consisting of 72...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2.0p Grid outerconnect 1 An n x n grid is an undirected graph consisting of 72 rows and 72 columns of vertices, as shown below. It has n vertices in total. We denote the vertex in the ith row and jth column by (i, j). All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points (i, j) for which i=1, i n. j 1, or j =n. (a) (b) In this exercise we consider a routing problem on grids that occurs when designing electronic circuit boards. Given a placement of transistors at given distinct vertices of a grid, we wish to determine if these transistors can be connected to the boundary of the grid, from where they connect to other components of the circuit board. To avoid short-circuits, each transistor should get its own connection to the boundary of the grid and the vertices and edges on this path should not be used by any other connections. We say that a grid with a given placement of transistors has an outerconnect if all transistors can be simultaneously connected to the boundary by a path that is vertex-disjoint from all the other paths. For example, the grid in (a) has an outerconnect, but the grid in (b) does not. Given a grid and a placement of m < n transistors at distinct vertices (, ), (2, Y),..., (Tm, Ym). the goal is to determine whether there is an outerconnect for the grid. Describe how the existence of an outerconnect (yes or no) can be determined by a single maximum flow computation. That is, describe how to construct a flow network G=(V, E) (with a sources, sinkt, and capacity function e for each edge) and how to define a value k from the given placement of m transistors, so that an outerconnect exists if and only there is a flow of value k in G. Describe the construction clearly. You do not have to prove its correctness. Hint: Find a way to prevent more than one unit of flow from going through any node of the grid, by representing such a node with two vertices joined by an edge of capacity 1. 2.0p Grid outerconnect 1 An n x n grid is an undirected graph consisting of 72 rows and 72 columns of vertices, as shown below. It has n vertices in total. We denote the vertex in the ith row and jth column by (i, j). All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points (i, j) for which i=1, i n. j 1, or j =n. (a) (b) In this exercise we consider a routing problem on grids that occurs when designing electronic circuit boards. Given a placement of transistors at given distinct vertices of a grid, we wish to determine if these transistors can be connected to the boundary of the grid, from where they connect to other components of the circuit board. To avoid short-circuits, each transistor should get its own connection to the boundary of the grid and the vertices and edges on this path should not be used by any other connections. We say that a grid with a given placement of transistors has an outerconnect if all transistors can be simultaneously connected to the boundary by a path that is vertex-disjoint from all the other paths. For example, the grid in (a) has an outerconnect, but the grid in (b) does not. Given a grid and a placement of m < n transistors at distinct vertices (, ), (2, Y),..., (Tm, Ym). the goal is to determine whether there is an outerconnect for the grid. Describe how the existence of an outerconnect (yes or no) can be determined by a single maximum flow computation. That is, describe how to construct a flow network G=(V, E) (with a sources, sinkt, and capacity function e for each edge) and how to define a value k from the given placement of m transistors, so that an outerconnect exists if and only there is a flow of value k in G. Describe the construction clearly. You do not have to prove its correctness. Hint: Find a way to prevent more than one unit of flow from going through any node of the grid, by representing such a node with two vertices joined by an edge of capacity 1.
Expert Answer:
Answer rating: 100% (QA)
To determine the existence of an outerconnect using a single maximum flow computation we can constru... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Are there any advantages using e-books rather than printed books?
-
An n ? n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in Figure 26.11. We denote the vertex in the i th row and the j th column by (I, j). All vertices in a...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
A compound with molecular formula C 17 H 36 exhibits a 1 H NMR spectrum with only one signal. How many signals would you expect in the 13C NMR spectrum of this compound?
-
The kinetic sculpture requires that each of the three pinned beams be in perfect balance at all times during its slow motion. If each member has a uniform weight density and length L, determine the...
-
The blue samurai, a japanese restraurant, has an asset turnover of 3.5 the total assets were 95,000 what are net sales for the blue samurai?
-
In stepwise regression, we specify that \(F_{\mathrm{IN}} \geq F_{\mathrm{OUT}}\left( ight.\) or \(t_{\mathrm{IN}} \geq t_{\mathrm{OUT}}\) ). Justify this choice of cutoff values.
-
A hotel pays an income tax rate of 28% on its profits. The hotel seeks an after-tax profit of $40,000 per month. Rounded up to the nearest dollar, what is the amount of before-tax profit the hotel...
-
Two speeding lead bullets, one of mass 13.0 g moving to the right at 320 m/s and one of mass 7.95 g moving to the left at 385 m/s, collide head-on, and all the material sticks together. Both bullets...
-
Ralph usually buys one pizza and two colas from the local pizzeria. The pizzeria announces a special: All pizzas after the first one is half-price. Show the original and new budget lines. What can...
-
1. Assume an ideal pulley (i.e. no mass) in the following system, draw FBD and write EOM for X and x2. Assume that X and x are defined in spring relaxed positions as their reference. Ideal pulley eee...
-
An insurance company crashed four cars in succession at 5 miles per hour. The cost of repair for each of the four crashes was \($422\), \($454\), \($419\), \($215\). Compute the range, sample...
-
A concrete mix is designed to withstand 3000 pounds per square inch (psi) of pressure. The following data represent the strength of nine randomly selected casts (in psi). 3950, 4080, 3300, 3100,...
-
Compute the range and sample standard deviation for the strength of this concrete (in psi). 3930, 4080, 3500, 3000, 2950, 3870, 4080, 4040
-
Sample: 25, 14, 1, 5, 10 Find the population mean or sample mean as indicated.
-
An insurance company crashed four cars of the same model at 5 miles per hour. The cost of repair for each of the four crashes was \($434\), \($413\), \($452\), and \($241\). Compute the mean, median,...
-
Calculate dy/dx at the point (4,4) at the point (4,4) on the curve 2 cos(x + y) = cos x - cos y (use fraction)
-
Dawson Companys balance sheet information at the end of 2019 and 2020 is as follows: Additional information: The company did not issue any common stock during 2020. Required : Next Level Fill in the...
-
Give a non recursive algorithm that performs an in order tree walk. An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes...
-
Show that the worst-case running time of HEAPSORT is (n lg n).
-
Prove that RSA is multiplicative in the sense that P A (M 1 ) P A (M 2 ) P A (M 1 M 2 ) (mod n). Use this fact to prove that if an adversary had a procedure that could efficiently decrypt 1 percent...
-
Understanding the Feds actions that are needed to stabilize the interest rate The diagram below shows three different money demand curves and a target interest rate i*. Fill in the table below using...
-
This section looks at US recessions over the past 60 years. To work out this problem, first obtain quarterly data on US output growth for the period 1960 to the most recent data from www.bea.gov....
-
This question asks you to examine the movements of investment and consumption before, during and after the recession of 2001. It also asks you to consider the response of investment and consumption...
Study smarter with the SolutionInn App