The Library
On the traveling salesman problem with a relaxed Monge matrix
Tools
UNSPECIFIED (1998) On the traveling salesman problem with a relaxed Monge matrix. INFORMATION PROCESSING LETTERS, 67 (5). pp. 231-237. ISSN 0020-0190.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
Official Date: | 15 September 1998 | ||||
Dates: |
|
||||
Volume: | 67 | ||||
Number: | 5 | ||||
Number of Pages: | 7 | ||||
Page Range: | pp. 231-237 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |