An approximation algorithm for computing longest paths
We show that the color-coding method of Alon et al. [Journal of the ACM 42 (1995) 844], in its version specialized to compute simple paths of a specified cardinality k, can be extended both to approximate the maximum cardinality of the simple paths, when the source and the destination of the paths are given, and also to address the presence of arc lengths (the existence of the last extension was outlined by the authors for a more general color-coding algorithm, but it was not explicitly described, and its time complexity was not discussed). The extensions are then used to derive approximation results for the general longest path problem.
longest path color-coding method heuristics