A linear time algorithm for the longest (s-t)-path problem restricted to partial k-trees
Manrique Mata-Montero, J.A. Ellis · Unisa Institutional Repository (University of South Africa) · 1994
The Longest (s-t)-path Problem, a known NP-complete set, is shown to admit a linear time solution when the instances of the problem are restricted to partial k-trees. This class of graphs is defined and some of the properties of partial k-trees, those needed for our algorithm are proved.