Let G = (V, E) be a directed acyclic graph modeling a communication network. Each link...

Let G = (V, E) be a directed acyclic graph modeling a communication network. Each link e in E is associated with two parameters, w(e) and d(e), where w(e) is a non-negative number representing the cost of sending a unit-sized packet through e, and d(e) is an integer between 1 and D representing the time (or delay) needed for transmitting a packet through e. Design an algorithm to find a route for sending a packet between a given pair of nodes in G such that the total delay is no more than k and the total cost is minimized. Your algorithm should run in O(k(|E| + |V |)) time and O(k|V |) space (additional to space for storing the graph). Hint: It is possible to use a linear time (i.e., O(n + m) time) algorithm called topological sort to compute the shortest path between any pair of vertices in a unit-weighted (i.e., all edges have weight 1) graph with n vertices and m edges.

Actually the question is this much only. I have been given HW and this question has been asked. I am unable to understand this that is why I posted here.

Solutions

Expert Solution

Summary of question:

According to question you will be given an acyclic graph (can be treated as directed tree) because no cylcles will be there in the graph.

After that for each edge in that graph you will be given 2 values ( w, d ) where "w" will tell you the cost it takes to move from one vertex to another vertex and "d" will tell you the time it take.

So, you have to comeup with an algorithm that can minimize the cost of sending the packet from one point to another and time taken should be less than "k".

Algorithm:

Algorithm:

We will find the cost it will take to reach from source to destination in minimum time

Store this answer in a variable say min_cost

Now we will find the cost it will take if time taken is 1 more than the minimum time, using BFS

Find minimum of previous(min_cost) and now calculated cost

And increment the time by 1

Repeate until time becomes greater than "k"

The cost we will get, will be the minimum cost

Time complexity will be O( k * (|V|+|E| ) ) in worst case

Space complexity will be O( |V| ) because BFS use queue to store values

venereology answered 6 months ago

Next > < Previous

Related Solutions

Let G = (V, E) be a directed graph, with source s ∈ V, sink t...

Let G = (V, E) be a directed graph, with source s ∈ V, sink t ∈ V, and nonnegative edge capacities {ce}. Give a polynomial-time algorithm to decide whether G has a unique minimum s-t cut (i.e., an s-t of capacity strictly less than that of all other s-t cuts).

A DAG is a directed graph that contains no directed cycles. Define G = (V, E)...

A DAG is a directed graph that contains no directed cycles. Define G = (V, E) in which V is the set of all nodes as {v1, v2, ..., vi , ...vn} and E is the set of edges E = {ei,j = (vi , vj ) | vi , vj ∈ V} . A topological order of a directed graph G = (V, E) is an ordering of its nodes as {v1, v2, ..., vi , ...vn} so that...

You are given a directed graph G(V,E) with n vertices and m edges. Let S be...

You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.

. Provide a weighted directed graph G = (V, E, c) that includes three vertices a,...

. Provide a weighted directed graph G = (V, E, c) that includes three vertices a, b, and c, and for which the maximum-cost simple path P from a to b includes vertex c, but the subpath from a to c is not the maximum-cost path from a to c

ii. Let G = (V, E) be a tree. Prove G has |V | − 1...

ii. Let G = (V, E) be a tree. Prove G has |V | − 1 edges using strong induction. Hint: In the inductive step, choose an edge (u, v) and partition the set vertices into two subtrees, those that are reachable from u without traversing (u, v) and those that are reachable from v without traversing (u, v). You will have to reason why these subtrees are distinct subgraphs of G. iii. What is the total degree of a...

Let G a graph of order 8 with V (G) = {v1, v2, . . ....

Let G a graph of order 8 with V (G) = {v1, v2, . . . , v8} such that deg vi = i for 1 ≤ i ≤ 7. What is deg v8? Justify your answer. Please show all steps thank you

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈...

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈ V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v). (a) Design an algorithm that returns a list containing the neighbourhood degree for each node v ∈...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. a) Draw a maximal plane graphs on six vertices. b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether...

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.) Determine, for a given graph G = V,E and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G =...

Subjects