Longest Path in a Graph: Difference between revisions
Jump to navigation
Jump to search
(Created page with "=Internal= * Graphs =Overview=") |
No edit summary |
||
| Line 1: | Line 1: | ||
=External= | |||
* https://en.wikipedia.org/wiki/Longest_path_problem | |||
* https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/ | |||
=Internal= | =Internal= | ||
* [[Graphs#Graph_Algorithms|Graphs]] | * [[Graphs#Graph_Algorithms|Graphs]] | ||
=Overview= | =Overview= | ||
The longest path problem is an NP-Hard problem for general graphs. However, the longest path can be computed on O(n) time for directed acyclic graphs. | |||
Revision as of 04:38, 9 November 2021
External
- https://en.wikipedia.org/wiki/Longest_path_problem
- https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
Internal
Overview
The longest path problem is an NP-Hard problem for general graphs. However, the longest path can be computed on O(n) time for directed acyclic graphs.