Longest path problem
id:
longest-path-problem-243-5900249
title:
Longest path problem
text:
In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the deci
brand slug:
wiki
category slug:
encyclopedia
description:
Problem of finding the longest simple path for a given graph
original url:
https://en.wikipedia.org/wiki/Longest_path_problem
date created:
date modified:
2024-01-02T01:59:15Z
main entity:
{"identifier":"Q2916352","url":"https://www.wikidata.org/entity/Q2916352"}
image:
fields total:
13
integrity:
14