Darts and hoopla board design

被引:7
作者
Curtis, SA [1 ]
机构
[1] Oxford Brookes Univ, Dept Comp, Oxford OX33 1HX, England
关键词
algorithms; combinatorial problems; travelling salesman;
D O I
10.1016/j.ipl.2004.06.005
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Dartboard design can be seen as an instance of the travelling salesman problem with maximum costs. This paper presents a simple yet optimal greedy algorithm to arrange numbers on both circular dartboards and linear hoopla boards. As a result, it identifies a class of polynomially solvable travelling salesman problems. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码:53 / 56
页数:4
相关论文
共 6 条
[1]  
[Anonymous], MATH GAZETTE
[2]   SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].
CARPANETO, G ;
TOTH, P .
MANAGEMENT SCIENCE, 1980, 26 (07) :736-743
[3]   ARRANGING N-DISTINCT NUMBERS ON A LINE OR A CIRCLE TO REACH EXTREME TOTAL VARIATIONS [J].
CHAO, CC ;
LIANG, WQ .
EUROPEAN JOURNAL OF COMBINATORICS, 1992, 13 (05) :325-334
[4]  
COHEN GL, 2001, ELECTRON J COMB, V8, pR4
[5]  
EISELT HA, 1991, J OPER RES SOC, V42, P113, DOI 10.2307/2583175
[6]  
SINGMASTER D., 1980, B I MATH ITS APPL, V16, P93