Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Solving the Longest Simple Path Problem with Constraint-Based Techniques
verfasst von : Quang Dung Pham, Yves Deville
Erschienen in: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The longest simple path problem on graphs arises in a variety of context, e.g., information retrieval, VLSI design, robot patrolling. Given an undirected weighted graph
G
= (
V
,
E
), the problem consists of finding the longest simple path (i.e., no vertex occurs more than once) on
G
. We propose in this paper an exact and a tabu search algorithm for solving this problem. We show that our techniques give competitive results on different kinds of graphs, compared with recent genetic algorithms.