The Library
On the traveling salesman problem with a relaxed Monge matrix
Tools
Tools
Tools
UNSPECIFIED (1998) On the traveling salesman problem with a relaxed Monge matrix. INFORMATION PROCESSING LETTERS, 67 (5). pp. 231-237. ISSN 0020-0190
Full text not available from this repository.Abstract
We show that the traveling salesman problem with a symmetric relaxed Monge matrix as distance matrix is pyramidally solvable and can thus be solved by dynamic programming. Furthermore, we present a polynomial time algorithm that decides whether there exists a renumbering of the cities such that the resulting distance matrix becomes a relaxed Monge matrix. (C) 1998 Elsevier Science B.V. All rights reserved.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Journal or Publication Title: | INFORMATION PROCESSING LETTERS |
| Publisher: | ELSEVIER SCIENCE BV |
| ISSN: | 0020-0190 |
| Date: | 15 September 1998 |
| Volume: | 67 |
| Number: | 5 |
| Number of Pages: | 7 |
| Page Range: | pp. 231-237 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/15301 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
