Dependency Graphs Math Example 4

Follow the full solution, then compare it with the other examples linked below.

Example 4

medium

A project has tasks with dependencies:

B

depends on

A

;

C

depends on

A

;

D

depends on

B

and

C

. What is the minimum number of time steps needed if independent tasks can run in parallel?

Solution

1
The critical path is $A \to B \to D$ or $A \to C \to D$ , both of length 3.
2
Step 1: $A$ . Step 2: $B$ and $C$ in parallel. Step 3: $D$ . So the minimum is 3 time steps.

Answer

3 \text{ time steps}

The minimum number of time steps equals the length of the longest path (critical path) in the dependency graph. Parallelism helps but cannot shorten the critical path.

About Dependency Graphs

A dependency graph is a directed graph where nodes are variables and arrows show which variables directly influence which others.

Learn more about Dependency Graphs →

More Dependency Graphs Examples

Example 1 easy

Three tasks have the following dependencies: Task B depends on Task A, and Task C depends on Task B.

Example 2 medium

Given the dependencies: [formula] depends on [formula] and [formula]; [formula] depends on [formula]

Example 3 medium

Tasks [formula], [formula], [formula], [formula]. What is the minimum number of stages to complete a

Example 5 hard

Given the dependency graph with edges [formula], [formula], [formula], [formula], [formula], [formul

← All Dependency Graphs Examples Dependency Graphs Concept

Related Concepts

Functional Dependency