Graph Theory37 sections · 1633 units
Open in CourseQuiz: DP on DAGs
Knowledge check
Check Your Understanding
You want the longest path from node to node in a DAG with nodes and edges. You process nodes in topological order and relax edges. What is the time complexity?
- A. because you consider all permutations
- B. because you relax all edges for each node
- C. because you compare all pairs
- D. because each node and edge is processed once