z-logo
open-access-imgOpen Access
An O(nlogn/logw) Time Algorithm for Ridesharing
Author(s) -
Yijie Han,
Chen Sun
Publication year - 2021
Publication title -
computer and information science
Language(s) - English
Resource type - Journals
eISSN - 1913-8997
pISSN - 1913-8989
DOI - 10.5539/cis.v14n1p8
Subject(s) - computer science , vertex (graph theory) , carry (investment) , algorithm , time complexity , graph , theoretical computer science , finance , economics
In the ridesharing problem different people share private vehicles because they have similar itineraries. The objective of solving the ridesharing problem is to minimize the number of drivers needed to carry all load to the destination. The general case of ridesharing problem is NP-complete. For the special case where the network is a chain and the destination is the leftmost vertex of the chain, we present an O(nlogn/logw) time algorithm for the ridesharing problem, where w is the word length used in the algorithm and is at least logn. Previous achieved algorithm for this case requires O(nlogn) time.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here