Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

problem 1: Let G = (V,E) be a graph for which all nodes have degree 5 and where G is 5-edge is connected.

a) Show that the vector x which is indexed by the edges E and for which xe= 1/5 for all e in E is in the Perfect Matching Polytope PPM.

b) Use your result in a) to show that G must have a perfect matching.

c) Show that b) may not be true if G is only 1-edge connected (but still has degree 5 everywhere) by giving an ex of such a graph G which has no perfect matching.
 
problem 2:

a) Find the shortest paths from r to all other nodes in the digraph G = (V,E) shown below using the Bellman-Ford algorithm (as taught in class). Please show your work, and draw the final shortest dipath tree on a copy of a diagram of the digraph.

1186_bellman ford algorithm.jpg

b) Using the potential y found in a), find a new set of costs c* for G which are non-negative, and preserve shortest dipaths.  

problem 3: Demonstrate that Dijkstra’s algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for which it fails. You must also demonstrate that Dijkstra’s algorithm fails on your ex.
 
problem 4: Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram which shows your solution on the digraph, and states its final cost.

1162_digraph.jpg


problem 5:

a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by using potentials: 

i) Show there is a potential y* for the new costs for which the paths in the tree to each node v have cost  y*v, and

ii) describe why this proves it. What is the relationship between the shortest path distances of the modified problem and those of the original problem? 
 
b) Can adding a constant k to the length of every arc coming out from a non-root node produce a change in the shortest path tree?  Justify your answer.
 
problem 6: Normally a potential y satisfies yr = 0 and 0  ≥ yw – cvw –yv. Given an integer K ≥ 0, define a K-potential to be an array y that satisfies yr = 0 and K ≥ yw – cvw –yv. Show that for a K-potential y we have that for each node v, yv is within Kn of being the cost of an optimal r-v dipath, i.e. show c(P) + Kn ≥ yv for any r to v dipath P in G.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91057

Have any Question? 


Related Questions in Computer Engineering

In the life model in the computer science section of the

In the Life model in the Computer Science section of the NetLogo models library, find a pattern where there are no more than 10 green cells to begin with but after 10 time steps there are at least 100 green cells. Also, ...

Why would a customer give contractors instructions in the

Why would a customer give contractors instructions in the RFP to submit their proposals according to a standard format? Answer in 4-5 sentences.

Over the course of the past 8 weeks has your view or

Over the course of the past 8 weeks, has your view or conception of ethics changed in any way? If yes, is there a specific moment you can identify and describe that triggered the change (a reading(s), or posting(s), disc ...

The registration area has just opened at large convention

The registration area has just opened at large convention of building contractors in New York. There are 600 people arriving per hour (exponential interarrival times), and their cost of waiting in queue is valued at $40 ...

What is the total delay latency for a frame of size 5

What is the total delay (latency) for a frame of size 5 million bits that is being sent on a link with 10 routers each having a queuing time of 2 μs and a processing time of 1 μs. The length of the link is 2000 Km. The s ...

This exercise examines deterministic packet selection

This exercise examines deterministic packet selection. Assume that the packet header contains spaces for routers to enter their IP addresses. a. Suppose the header contains space for 30 router addresses. Initially, these ...

After the dhke alice and bob possess a mutual secret point

After the DHKE, Alice and Bob possess a mutual secret point R = (x,y). The modulus of the used elliptic curve is a 64-bit prime. Now, we want to derive a session key for a 128-bit block cipher. The session key is calcula ...

1 in an internet we change the lan technology to a new one

1. In an internet, we change the LAN technology to a new one. Which layers in the TCP/IP protocol suite need to be changed? 2. Assume that an application-layer protocol is written to use the services of UDP. Can the appl ...

1 discuss a good security auditing system2 compare or

1. Discuss a good security auditing system. 2. Compare or discuss the differences between any two security systems. 3. Discuss human error or human factors as a major security threat. 4. What is the best way to deal with ...

1 what general attributes do organizations seek in

1. What general attributes do organizations seek in candidates when hiring information security professionals across all positions? Prioritize the list and justify your ranking. 2. What are the critical considerations wh ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen