The Floyd-Warshall Algorithm, the AP and the TSP

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We use admissible permutations and a variant of the Floyd-Warshall algorithm to obtain an optimal solution to the Assignment Problem. Using another variant of the F-W algorithm, we obtain an approximate solution to the Traveling Salesman Problem. We also give a sufficient condition for the approximate solution to be an optimal solution.
Text in Word 2000, math in MathType 4.0, sent in a PDF file written in Acrobat 5.0, 23 pages

Keywords

Combinatorics, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/62763

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0111309
 http://arxiv.org/abs/math/0111309

Collections

arXiv