Provide again a polynomial time algorithm

Assignment Help Computer Engineering

Reference no: EM132141247

Suppose we are given a directed graph G = (V, E), a set of nodes A V (denoted as people) and a set of nodes B V (denoted as exit). Assume A and B are disjoint. We want to find a schedule such that every person can escape to an exit node. More specifically, a schedule is a set of paths in G so that:

Every path contains exactly one node in A.

Each node in A is the first node of the corresponding path.

For each path, the last node is an exit node.

All the paths are edge-disjoint.

Given G, A, B, provide a polynomial time algorithm that decides whether such a schedule exists.

Suppose the third condition is changed to: All the paths are node-disjoint.

Provide again a polynomial time algorithm that decides whether such a schedule exists. Provide an example with the same G, A, B such that in this instance, the answer is "yes" to part (a) but "no" to part (b).

Reference no: EM132141247

Questions Cloud

Compare the time for a query and response for a complete : Compare the time for a query and response for a complete DNS query and response (to all required nameservers) if M=1, M=2, and M=3.

How much will it cost to provide disk space : At contemporary memory pricing of $7 / GB, how much will it cost to fill the machine? Knowing what you know about virtual memory.

How this special computer can be used to sort the given n : Suppose you are given n positive integers to sort on a special computer which has access to special memory containing p slots.

Create an algorithm for telling if l and m store the same : Create an algorithm for telling if L and M store the same sequence of elements (but perhaps with different starting points).

Provide again a polynomial time algorithm : Suppose we are given a directed graph G = (V, E), a set of nodes A V (denoted as people) and a set of nodes B V (denoted as exit).

What is the running time of your algorithm : Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

How many total packets are sent with stop-and-wait : Assume that ACKs are never lost. How many total packets (including retransmissions) are sent with stop-and-wait.

Design an algorithm to update the minimum spanning tre : Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.

What speedup is possible with pipelining : What is the maximum execution rate without pipelining? What speedup is possible with pipelining?

User Account

All Pages