On the traveling salesman problem with a relaxed Monge matrix
UNSPECIFIED (1998) On the traveling salesman problem with a relaxed Monge matrix. INFORMATION PROCESSING LETTERS, 67 (5). pp. 231-237. ISSN 0020-0190Full text not available from this repository.
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|
|Date:||15 September 1998|
|Number of Pages:||7|
|Page Range:||pp. 231-237|
Actions (login required)