1) Consider a directed graph G = (V,E) in which V is partitioned into two sets of nodes, D andS. The nodes in D are disaster-prone areas and the nodes in S are safe areas. We have to findan evacuation route from each node in D to some node of S, and the routes must have lowcongestion overall. To satisfy these, the evacuation routes must satisfy the following conditions.(i) each node in D is the st
...[Show More]
1) Consider a directed graph G = (V,E) in which V is partitioned into two sets of nodes, D and
S. The nodes in D are disaster-prone areas and the nodes in S are safe areas. We have to find
an evacuation route from each node in D to some node of S, and the routes must have low
congestion overall. To satisfy these, the evacuation routes must satisfy the following conditions.
(i) each node in D is the start of one route,
(ii) each route ends at a node in S, and
(iii) the routes do not share any edges.
Design an algorithm to decide in polynomial time whether a set of evacuation routes exist.
2) A company has ‘k’ projects that are to be done. It hired ‘n’ employees to complete these
projects. Each project requires a number of employees specified by [ai,bi] , where ai is the
minimum number of employees needed to complete the project and bi is the maximum number
of employees needed in the project. Each employee is suitable for some particular projects
based on their skillset.
Given a list of employees, a list of projects, the ranges of each project [ai,bi] and a list of suitable
projects for each employee, give an efficient algorithm to determine whether a suitable pairing of
employees and projects is possible such that
i) Each employee can be assigned to only project
ii)Each project has at least ai employees and at most bi employees.
[Show Less]
