On the Shared Transportation Problem: Computational Hardness and Exact Approach - Université de technologie de Compiègne Access content directly
Journal Articles International Journal of Foundations of Computer Science Year : 2023

On the Shared Transportation Problem: Computational Hardness and Exact Approach

Abstract

In our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the [Formula: see text]-path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm.
Fichier principal
Vignette du fichier
main.pdf (461.02 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04097811 , version 1 (15-05-2023)

Identifiers

Cite

Tom Davot, Rodolphe Giroudeau, Jean-Claude König. On the Shared Transportation Problem: Computational Hardness and Exact Approach. International Journal of Foundations of Computer Science, In press, pp.1-16. ⟨10.1142/S0129054123410058⟩. ⟨hal-04097811⟩
0 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More