forbidden neighborhood

The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 3D Grids

  • Anja Fischer
  • Philipp Hungerländer
  • Anna Jellen
    • Categories Combinatorial Optimization Tags , , ,

    We study the traveling salesperson problem with forbidden neighborhoods (TSPFN) on regular three-dimensional grids. The TSPFN asks for a shortest tour over all grid points such that successive points along a tour have at least some given distance. We present optimal solutions and explicit construction schemes for the Euclidean TSP and the TSPFN where edges … Read more

    Closed Almost Knight’s Tours on 2D and 3D Chessboards

  • Michael Firstein
  • Anja Fischer
  • Philipp Hungerländer
    • Categories Combinatorial Optimization Tags , ,

    Let a (generalized) chessboard in two or three dimensions be given. A closed knight’s tour is defined as a Hamiltonian cycle over all cells of the chessboard where all moves are knight’s moves, i.,e. have length 5^0.5. It is well-characterized for which chessboard sizes it is not possible to construct a closed knight’s tour. On … Read more