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

5 igrp supports a feature , 5 IGRP supports a feature that permits traffic ...

5 IGRP supports a feature that permits traffic to be distributed among up to 6 (4 default) paths to give greater allover throughput and reliability. What is this called? Ans) An

WOrkstation, Interdepences of workstation hardware and software

Interdepences of workstation hardware and software

Explain about nonboundary-level masking, Q. Explain about Nonboundary-Level...

Q. Explain about Nonboundary-Level Masking? Nonboundary-Level Masking Bytes in the IP address that correspond to 255 in the mask will be repeated in the subnet addres

What is a tag, In HTML, a tag shows the browser what to do. When you write ...

In HTML, a tag shows the browser what to do. When you write an HTML page, you enter tags for lot of  reasons -- to change the appearance of text, to show a graphic, or to make a co

Digital encoding scheme, what are the applications of different encoding sc...

what are the applications of different encoding schemes

Describe the term disaster management as security threats, Describe the ter...

Describe the term Disaster Management as security threats Making and testing backups regularly could be the simplest and easiest of all the security measures. But a new questio

What is icmp, What is ICMP? ICMP is Internet Control Message Protocol. ...

What is ICMP? ICMP is Internet Control Message Protocol. It gives messaging and communication for protocols within the TCP/IP stacks. This is also the protocol that manages err

What is meant by symmentric multiprocessing (smp), It treats all processors...

It treats all processors as equivalent. Any processor can do the work of any other processor. Applications are separated into threads that can run simultaneously on any available p

Define remote procedure call (rpc), RPC adumbrates the intricacies of the ...

RPC adumbrates the intricacies of the network by using the ordinary procedure call mechanism familiar to each programmer. A client process calls a function on a remote server and

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