%0 Journal Article %1 garfinkel1977minimizing %A Garfinkel, Robert S. %D 1977 %J Operations Research %K circulant hamiltonian tsp %N 5 %P 741--751 %R 10.1287/opre.25.5.741 %T Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems %V 25 %X 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.

@article{garfinkel1977minimizing, 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. }, added-at = {2016-12-04T08:25:21.000+0100}, author = {Garfinkel, Robert S.}, biburl = {https://www.bibsonomy.org/bibtex/288600b92ee9b07c247c1b164facabed8/ytyoun}, doi = {10.1287/opre.25.5.741}, interhash = {ebb856e22f9bb55f6bcb00417340d1c1}, intrahash = {88600b92ee9b07c247c1b164facabed8}, journal = {Operations Research}, keywords = {circulant hamiltonian tsp}, number = 5, pages = {741--751}, timestamp = {2016-12-29T04:40:44.000+0100}, title = {Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems}, volume = 25, year = 1977 }