Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ejor.2008.04.011 | European Journal of Operational Research |
Keywords | Field | DocType |
Traveling salesperson problem,Bottleneck traveling salesperson problem,Multiple objectives,Solvable cases,Halin graphs,Computational complexity | Graph theory,Bottleneck,Graph,Mathematical optimization,Multiobjective programming,Travelling salesman problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
196 | 1 | 0377-2217 |
Citations | PageRank | References |
8 | 0.56 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Özgür Özpeynirci | 1 | 55 | 7.00 |
| Murat Köksalan | 2 | 531 | 48.82 |