Article citationsMore>>

Gu, Q.-P., Liang, L. and Zhang, G. (2016) Algorithmic Analysis for Ridesharing of Personal Vehicles. Proc. of COCOA 2016, LNCS 10043, 438-452. https://doi.org/10.1007/978-3-319-48749-6_32

has been cited by the following article:

• TITLE: A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees

  AUTHORS: Yiming Li, Huiqiang Lu, Zhiqian Ye, Xiao Zhou

  KEYWORDS: Dynamic Programming Algorithm, Rideshare, Tree

  JOURNAL NAME: Journal of Applied Mathematics and Physics, Vol.5 No.9, September 15, 2017

  ABSTRACT: We deal with the problem of sharing vehicles by individuals with similar itineraries which is to find the minimum number of drivers, each of which has a vehicle capacity and a detour to realize all trips. Recently, Gu et al. showed that the problem is NP-hard even for star graphs restricted with unique destination, and gave a polynomial-time algorithm to solve the problem for paths restricted with unique destination and zero detour. In this paper we will give a dynamic programming algorithm to solve the problem in polynomial time for trees restricted with unique destination and zero detour. In our best knowledge it is a first polynomial-time algorithm for trees.