Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
- 1 October 1977
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 25 (5) , 741-751
- https://doi.org/10.1287/opre.25.5.741
Abstract
We address the problem of wallpapering a room so as to minimize the paper wasted. We show that the problem is equivalent to finding a shortest hamiltonian chain in a highly structured graph. When the chain connects two equivalent nodes traveling salesman problem, the \"nearest-neighbor\" technique yields an optimal solution.Keywords
This publication has 0 references indexed in Scilit: