An approximation algorithm for computing longest paths

An approximation algorithm for computing longest paths

0.00 Avg rating0 Votes
Article ID: iaor20042816
Country: Netherlands
Volume: 148
Issue: 3
Start Page Number: 584
End Page Number: 590
Publication Date: Aug 2003
Journal: European Journal of Operational Research
Authors:
Keywords: heuristics
Abstract:

We show that the color-coding method of Alon et al., 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.

Reviews

Required fields are marked *. Your email address will not be published.