Longest Path
المؤلف:
Zamfirescu, T
المصدر:
"On Longest Paths and Circuits in Graphs." Math. Scand. 38
الجزء والصفحة:
211-239
11-5-2022
1551
Longest Path
The longest path problem asks to find a path of maximum length in a given graph. The problem is NP-complete, but there exists an efficient dynamic programming solution for acyclic digraphs.
The detour matrix is a real symmetric matrix whose 
th entry is the length of the longest path from vertex 
to vertex 
.
For a traceable graph, longest paths correspond to Hamiltonian paths.
Finding a longest path is challenging for stacked book graphs and Apollonian networks.
REFERENCES
Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
