An approximation algorithm for computing longest paths.

DOI10.1016/S0377-2217(02)00433-2zbMath1035.90075OpenAlexW2064110920MaRDI QIDQ1812006

Maria Grazia Scutellà

Publication date: 18 June 2003

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00433-2

zbMATH Keywords

HeuristicsLongest pathColor-coding method

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Minimal functional routes in directed graphs with dependent edges ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ A genetic algorithm for the picture maze generation problem

Cites Work

• Unnamed Item
• On approximating the longest path in a graph
• A characterization of the minimum cycle mean in a digraph
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Graph minors. II. Algorithmic aspects of tree-width
• `` Strong NP-Completeness Results
• Color-coding

This page was built for publication: An approximation algorithm for computing longest paths.