Question

In: Computer Science

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.

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 1 year ago

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).

If G = (V, E) is a graph and x ∈ V , let G \...

If G = (V, E) is a graph and x ∈ V , let G \ x be the graph whose vertex set is V \ {x} and whose edges are those edges of G that don’t contain x. Show that every connected finite graph G = (V, E) with at least two vertices has at least two vertices x1, x2 ∈ V such that G \ xi is connected.

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

# Problem Description Given a directed graph G = (V, E), find the number of connected...

# Problem Description Given a directed graph G = (V, E), find the number of connected components in G. # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives two numbers `n` and `m`, describing the number of vertices and edges. Each of the following lines contains two numbers `a` and `b` meaning there is an edge (a,b) belong to E. All the numbers in a line are separated by...

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0...

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0 for any e in E, and a source vertex s. Use Dijkstra’s algorithm to calculate distance(s,v) for all of the vertices v in V. (You can implement your own priority queue or use the build-in function for C++/Python) # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <=...

Please use python: # Problem Description Given a directed graph G = (V, E), find the...

Please use python: # Problem Description Given a directed graph G = (V, E), find the number of connected components in G. # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives two numbers `n` and `m`, describing the number of vertices and edges. Each of the following lines contains two numbers `a` and `b` meaning there is an edge (a,b) belong to E. All the numbers in a line...

Let G be a connected graph and let e be a cut edge in G. Let...

Let G be a connected graph and let e be a cut edge in G. Let K be the subgraph of G defined by: V(K) = V(G) and E(K) = E(G) - {e} Prove that K has exactly two connected components. First prove that e cannot be a loop. Thus the endpoint set of e is of the form {v,w}, where v ≠ w. If ṽ∈V(K), prove that either there is a path in K from v to ṽ, or...

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