Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477295 | European Journal of Operational Research | 2009 | 7 Pages |
Abstract
In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Özgür Özpeynirci, Murat Köksalan,