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 ...