Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An approximation algorithm for the k-fixed depots problem

Abstract : In this paper, we consider the k-Depots Hamiltonian Path Problem (k-DHPP) of searching k paths in a graph G, starting from k fixed vertices and spanning all the vertices of G. We propose an approximation algorithm for solving the k-DHPP, where the underlying graph is cubic and 2-vertex-connected. Then, we prove the existence of a 5/3-approximation algorithm that gives a solution with total cost at most (5/3n - 4k-2/3). In this case, the proposed method is based upon searching for a perfect matching, constructing an Eulerian graph and finally a k paths solution, following the process of removing/adding edges. We also present an approximation algorithm for finding a shortest tour passing through all vertices in a factor-critical and 2-vertex connected graph. The proposed algorithm achieves a 7/6-approximation ratio where the principle of the method is based on decomposing the graph into a series of ears. (C) 2017 Published by Elsevier Ltd.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617899
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:16
Dernière modification le : samedi 17 septembre 2022 - 17:34:45

Identifiants

Collections

Citation

A. Giannakos, Mhand Hifi, R. Kheffache, Rachid Ouafi. An approximation algorithm for the k-fixed depots problem. Computers & Industrial Engineering, Elsevier, 2017, 111, pp.50-55. ⟨10.1016/j.cie.2017.06.022⟩. ⟨hal-03617899⟩

Partager

Métriques

Consultations de la notice

5