Reference no: EM131122435
(Minimum Weight Spanning Trees) Given a graph (N , A) and a weight wij for each arc (i, j), consider the problem of finding a spanning tree with minimum sum of arc weights. This is not a shortest path problem and in fact it is not even a special case of the minimum cost flow problem. However, it has a similar graph structure to the one of the shortest path problem. Note that the orientation of the arcs does not matter here. In particular, if (i, j) and (j, i) are arcs, any one of them can participate in a spanning tree solution, and the arc having greater weight can be a priori eliminated.
(a) Consider the problem of finding a shortest path from node 1 to all nodes with arc lengths equal to wij . Give an example where the shortest path spanning tree is not a minimum weight spanning tree.
(b) Let us define a fragment to be a subgraph of a minimum weight spanning tree; for example the subgraph consisting of any subset of nodes and no arcs is a fragment. Given a fragment F, let us denote by A(F) the set of arcs (i, j) such that either i or j belong to F, and if (i, j) is added to F no cycle is closed. Show that if F is a fragment, then by adding to F an arc of A(F) that has minimum weight over all arcs of A(F) we obtain a fragment.
(c) Consider a greedy algorithm that starts with some fragment, and at each iteration, adds to the current fragment F an arc of A(F) that has minimum weight over all arcs of A(F). Show that the algorithm terminates with a minimum weight spanning tree.
(d) Show that the complexity of the greedy algorithm is O(NA), where N is the number of nodes and A is the number of arcs.
(e) The Prim-Dijkstra algorithm is the special case of the greedy algorithm where the initial fragment consists of a single node.
Provide an O(N2), implementation of this algorithm. Hint: Together with the kth fragment Fk, maintain for each j /∈ Fk the node nk(i) ∈ Fk such that the arc connecting j and nk(i) has minimum weight
|
Explain what happens to the postmerger earnings
: Explain what happens to the postmerger earnings per share figure when a company with a relatively high P/E ratio acquires a company with a lower P/E ratio, assuming that the exchange ratio is based on current stock market prices and no synergy exists..
|
|
How would the general anti-avoidance rule affect transaction
: Over the past two years, your client, a lawyer in sole practice, has developed several software packages for the preparation of legal contracts. If tax is avoided, how would the general anti-avoidance rule affect the transactions?
|
|
What methods do financial analysts use to value merger
: What methods do financial analysts use to value merger candidates? What are the limitations of each method?
|
|
What are some of the reasons why firms merge with other firm
: What are some of the reasons why firms merge with other firms?
|
|
Finding a spanning tree with minimum sum of arc weights
: Provide an O(N2), implementation of this algorithm. Hint: Together with the kth fragment Fk, maintain for each j /∈ Fk the node nk(i) ∈ Fk such that the arc connecting j and nk(i) has minimum weight
|
|
Prepare an accounts payable subsidiary ledger report
: Prepare an accounts payable subsidiary ledger report (from the corrected accounts payable subsidiaryledger.
|
|
Difference between horizontal vertical conglomerate mergers
: Discuss the differences between the following types of mergers: a. Horizontal mergers b. Vertical mergers c. Conglomerate mergers
|
|
Give the values of the population parameters
: Consider a small population of N = 5 units, labeled 1, 2, 3, 4, 5, with respective y-values 3, 1, 0, 1, 5. Consider a simple random sampling design with a sample size n = 3.
|
|
Explain the process of preparing an operations budget
: Explain the process of preparing an operations budget. Describe the budgeting control process and explain how significant variances are determined. What are the forecasted revenues for the month?
|