Describe an efficient algorithm to find the paths

Assignment Help Computer Engineering

Reference no: EM132141188

Suppose we are given a directed graph G;

a) We want to find 3 edge disjoint paths from a designated starting vertex u to a specific destination vertex d (or determine that no such paths exist). Describe an efficient algorithm to find the paths and give the running time of your solution.

b) Now suppose we have three different destinations d1,d2 and d3. We want to find 3 paths from our start vertex u, one to each of the destinations and we want these 3 paths to be edge disjoint. Describe an efficient algorithm to find the paths and give the running time of your solution.

Reference no: EM132141188

Questions Cloud

What is the net cash flow in one year : Assume that an arbitrager can borrow up to $1,000,000 or €800,000. If an astute trader finds an arbitrage, what is the net cash flow in one year?

Which type of firewall will work with such packets : Suppose that incoming packets are encrypted with a symmetric key that only the sender and receiver know.

Growth rate of dividends : How do you calculate g, the growth rate of dividends, using the following variables? g=growth rate of future earnings and the growth in the common stockholders

Coupon rate of a particular bond : If current market yields in the bond market are above the coupon rate of a particular bond-what will happen to the intrinsic value (PV and market price)?

Describe an efficient algorithm to find the paths : We want to find 3 edge disjoint paths from a designated starting vertex u to a specific destination vertex d .

Uses of capm-capital assets pricing model : Consider investing in machinery that costs $ 1000 and generates in one year $ 1300, $ 1,100 or $ 900 with equal probability.

Compute what the average turnaround time will be : Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used.

What are the expected net percentage returns : If each stock is priced at $125, what are the expected net percentage returns on each stock to (1) a pension fund that does not pay taxes

Calculate equity valuation-gordon growth model : A company just paid a dividend of 2.30 to its shareholder. It estimates that future growth will be at 2%. What is the value of the stock

User Account

All Pages