Groupe d’études et de recherche en analyse des décisions

G-83-07

Finding the Shortest Cycle Through k Specified Nodes

et

Let G = (N,E) be an undirected graph where N is the set of nodes and E, the set of edges. Let C be a symmetrical distance matrix defined on N2 and K, a subset of N. This paper considers the problem of determining the shortest cycle containing each node of K exactly once and each node of N-K at most once. The problem is formulated as an integer linear program and solved by three different algorithms. Numerical results are reported.

, 11 pages