{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T04:43:00Z","timestamp":1683693780273},"reference-count":0,"publisher":"World Scientific Pub Co Pte Ltd","funder":[{"name":"National Agency for Research","award":["ANR-11-IDEX-0004-02"],"award-info":[{"award-number":["ANR-11-IDEX-0004-02"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"abstract":"<jats:p> 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\u00f6hmov\u00e1 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. <\/jats:p>","DOI":"10.1142\/s0129054123410058","type":"journal-article","created":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T16:39:48Z","timestamp":1683650388000},"page":"1-16","source":"Crossref","is-referenced-by-count":0,"title":["On the Shared Transportation Problem: Computational Hardness and Exact Approach"],"prefix":"10.1142","author":[{"given":"Tom","family":"Davot","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Technologie de Compi\u00e8gne, CNRS, Heudiasyc, (Heuristics and Diagnosis of Complex Systems), CS 60 319 - 60 203 Compi\u00e8gne Cedex, France"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[{"name":"LIRMM - CNRS UMR 5506 - Montpellier, France"}]},{"given":"Jean-Claude","family":"K\u00f6nig","sequence":"additional","affiliation":[{"name":"LIRMM - CNRS UMR 5506 - Montpellier, France"}]}],"member":"219","published-online":{"date-parts":[[2023,5,9]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123410058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T16:39:53Z","timestamp":1683650393000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123410058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,9]]},"references-count":0,"alternative-id":["10.1142\/S0129054123410058"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123410058","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,9]]}}}