Anzeige
Erschienen in:
01.05.2023
An approximation algorithm for the clustered path travelling salesman problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2023
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, we consider the clustered path travelling salesman problem. In this problem, we are given a complete graph \(G=(V,E)\) with an edge weight function w satisfying the triangle inequality. In addition, the vertex set V is partitioned into clusters \(V_1,\ldots ,V_k\) and s, t are two given vertices of G with \(s\in V_1\) and \(t\in V_k\). The objective of the problem is to find a minimum Hamiltonian path of G from s to t, where all vertices of each cluster are visited consecutively. In this paper, we deal with the case that the start-vertex and the end-vertex of the path on each cluster are both specified, and for it we provide a polynomial-time approximation algorithm.