traveling salesman problem

On cost matrices with two and three distinct values of Hamiltonian paths and cycles

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Polynomially testable characterization of cost matrices associated with a complete digraph on $n$ nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov~\cite{TARA81} obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices that can be … Read more

    Continuous Line Drawings via the Traveling Salesman Problem

  • Robert Bosch
  • Adrianne Herman
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Combinatorial Optimization Tags ,

    We describe how to use the traveling salesman problem (TSP) to create continuous line drawings of target pictures. Citation Dept. of Mathematics, Oberlin College, Oberlin, Ohio 44074 Article Download View Continuous Line Drawings via the Traveling Salesman Problem