Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph

P. Miliotis; G. Laporte; Y. Nobert

RAIRO - Operations Research - Recherche Opérationnelle (1981)

  • Volume: 15, Issue: 3, page 233-239
  • ISSN: 0399-0559

How to cite

top

Miliotis, P., Laporte, G., and Nobert, Y.. "Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph." RAIRO - Operations Research - Recherche Opérationnelle 15.3 (1981): 233-239. <http://eudml.org/doc/104787>.

@article{Miliotis1981,
author = {Miliotis, P., Laporte, G., Nobert, Y.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {computational comparison of methods; shortest complete cycle; circuit; equivalent Hamiltonian cycle problem; computational experience; graphs with random complete distance matrices},
language = {eng},
number = {3},
pages = {233-239},
publisher = {EDP-Sciences},
title = {Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph},
url = {http://eudml.org/doc/104787},
volume = {15},
year = {1981},
}

TY - JOUR
AU - Miliotis, P.
AU - Laporte, G.
AU - Nobert, Y.
TI - Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1981
PB - EDP-Sciences
VL - 15
IS - 3
SP - 233
EP - 239
LA - eng
KW - computational comparison of methods; shortest complete cycle; circuit; equivalent Hamiltonian cycle problem; computational experience; graphs with random complete distance matrices
UR - http://eudml.org/doc/104787
ER -

References

top
  1. 1. M. BELLMORE and G. L. NEMHAUSER, The Travelling Salesman Problem; a Survey, Operations Research, Vol. 16, 1968, pp. 538-558. Zbl0213.44604MR234711
  2. 2. N. CHRISTOFIDES, The Travelling Salesman Problem, published in "Combinatorial Optimisation" by CHRISTOFIDES et al., Wiley, 1979, pp. 131-149. Zbl0415.90057
  3. G. B. DANTZIG, D. R. FULKERSON and S. M. JOHNSON, Solution of a Larger Scale Traveling-Salesman Problem, Operations Research, Vol. 2, 1954, pp. 393-419. Zbl1187.90007MR70932
  4. 4. J. EDMONDS and E. JOHNSON, Matching, Euler Tours and the Chinese Postman, Mathematical Programming, Vol. 5, 1973, pp. 88-124. Zbl0281.90073MR321801
  5. 5. L. EULER, Commentationes Arithmeticae Collectae, Saint-Petersbourg, 1766, pp. 337-338. 
  6. 6. W. W. HARDGRAVE and G. L. NEMHAUSER, On the Relation between the TravellingSalesman Problem and the Longest Path Problem, Operations Research, Vol. 10, 1962, pp. 647-657. Zbl0124.36204MR143651
  7. 7. A . H . LAND and S. POWELL, Fortran Codes for Mathematical Programming, Wiley, 1973. Zbl0278.68036
  8. 8. P. MILIOTIS, Integer Programming Approaches to the Travelling Salesman Problem, Mathematical Programming, Vol. 10, 1976, pp. 367-378. Zbl0337.90041MR441337
  9. 9. P. MILIOTIS, Using Cutting Planes to Solve the Symmetrie Travelling SalesmanProblem, Mathematical Programming, Vol. 15, 1978, pp. 117-188. Zbl0393.90059MR1552870
  10. 10. J. D. MURCHLAND, A Fixed Matrix Method for all Shortest Distances in a DirectedGraph and for the Inverse Problem, Ph. D. Dissertation, Karlsruhe, 1970. MR321787

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.