Describe the steps involved in network simplex method, Computer Networking

Assignment Help:

QUESTION 1:

(a) Define what you understand by the following terms in Network Flows:

i) UnDirected Path
ii) Directed Path
iii) Directed Cycle.
iv) Tree

In each of the above, show the differences in terms of nodes and directions.

(b) In Radix Heap Algorithm, the technique of buckets is employed. However this idea is an extension of Dial's Algorithm. Analyse the complexity of Radix Heap Algorithm referring to:

1. Movement of nodes between buckets
2. Node Selection principle

QUESTION 2:

(a) Below is the algorithm of a flow decomposition algorithm.

begin
Initialize
while y ≠ Φ do
begin
              Select(s, y)
              Search(s, y)
              if a cycle C is found then do
              begin
                            let D = Capacity(C, y)
                            Add Flow(D, C) to cycle flows
                            Subtract Flow(D, C) from y.
              end
              if a path P is found then do
              begin
                           let D = Capacity(P, y)
                           Add Flow(D, P) to path flows
                           Subtract Flow(D, P) from y.
               end
end

Describe the complexity of the following:

i) Selecting the initial node,
ii) Finding a cycle or a path,
iii) Update step.

(b) Explain how Lower Bounds on Arc Flows are eliminated. Show your workings by a mathematical representation or otherwise.

(c) Refer to the diagram below, show how we could always provide a flow of at most 10 on Node 4.

                          1881_11.png

QUESTION 3:

(a) Briefly describe the steps involved in Network Simplex Method.

(b) Referring to Dial's Algorithm and assuming C, to be the Largest arc length, complete the table below.

Variables                                   Cost Value
Number of buckets needed
Time to create buckets.
Time to update d() and
buckets.
Time to find min.
Total running time.

(c) Using Kruskal's algorithm, find the minimum spanning tree of the graph as show in Figure 3.1.

                              1776_11.png

                                                       Figure 3.1

(d) Give mathematical models for the 0-1 knapsack problem and the bounded knapsack problem in Dynamic Programming.


QUESTION 4:

(a) Write down a Generic Label Correcting Algorithm.

(b) Explain how you could detect Negative Cost Cycles in a given set of flows.

(c) Prove that a Negative Cycle Algorithm terminates with an optimal flow.


Related Discussions:- Describe the steps involved in network simplex method

What is error control, What is Error Control ? Error control is both er...

What is Error Control ? Error control is both error detection and error correction. It allows the receiver to inform the sender of any frames lost or damaged in transmission an

Explain transparent bridges and learning bridges, Transparent Bridges & Lea...

Transparent Bridges & Learning Bridges - Builds table by examining destination as well as source address of each packet it receives - Learning bridges - If address is not

What is nic and wan, What is NIC and WAN? NIC is short for Network Inte...

What is NIC and WAN? NIC is short for Network Interface Card. This is a peripheral card that is joined to a PC in order to connect to a network. Each NIC has its own MAC addres

Importance of reliability engineering, The progress of any industry and ind...

The progress of any industry and indeed countries as well, today is linked to the effective performance of its equipments, processes and systems. Reliability engineering, not only

State the nonselective fading and selective fading, Nonselective fading and...

Nonselective fading and Selective fading Nonselective fading, is a fading in which all frequency methods of the received signal fluctuate in the similar proportions simultaneo

Describe in detail how rsvp actually works, Normal 0 false fa...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

General middleware in client server environment, What is General Middleware...

What is General Middleware in client server environment? Ans) It having the communication stacks, distributed directories, authentication services, network time, RPC, Queuing se

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd