An O(nlogn/logw) Time Algorithm for Ridesharing Article Swipe
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.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.5539/cis.v14n1p8
- https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014
- OA Status
- diamond
- References
- 8
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3118691141
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3118691141Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.5539/cis.v14n1p8Digital Object Identifier
- Title
-
An O(nlogn/logw) Time Algorithm for RidesharingWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-01-08Full publication date if available
- Authors
-
Yijie Han, Chen SunList of authors in order
- Landing page
-
https://doi.org/10.5539/cis.v14n1p8Publisher landing page
- PDF URL
-
https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014Direct OA link when available
- Concepts
-
Computer science, Vertex (graph theory), Carry (investment), Algorithm, Time complexity, Graph, Theoretical computer science, Economics, FinanceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
8Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3118691141 |
|---|---|
| doi | https://doi.org/10.5539/cis.v14n1p8 |
| ids.doi | https://doi.org/10.5539/cis.v14n1p8 |
| ids.mag | 3118691141 |
| ids.openalex | https://openalex.org/W3118691141 |
| fwci | 0.0 |
| type | article |
| title | An O(nlogn/logw) Time Algorithm for Ridesharing |
| biblio.issue | 1 |
| biblio.volume | 14 |
| biblio.last_page | 8 |
| biblio.first_page | 8 |
| topics[0].id | https://openalex.org/T11942 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9998999834060669 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2203 |
| topics[0].subfield.display_name | Automotive Engineering |
| topics[0].display_name | Transportation and Mobility Innovations |
| topics[1].id | https://openalex.org/T12392 |
| topics[1].field.id | https://openalex.org/fields/14 |
| topics[1].field.display_name | Business, Management and Accounting |
| topics[1].score | 0.9966999888420105 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1406 |
| topics[1].subfield.display_name | Marketing |
| topics[1].display_name | Sharing Economy and Platforms |
| topics[2].id | https://openalex.org/T12546 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9865000247955322 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2215 |
| topics[2].subfield.display_name | Building and Construction |
| topics[2].display_name | Smart Parking Systems Research |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.8319384455680847 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C80899671 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6753331422805786 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[1].display_name | Vertex (graph theory) |
| concepts[2].id | https://openalex.org/C2776299755 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6054471135139465 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q432449 |
| concepts[2].display_name | Carry (investment) |
| concepts[3].id | https://openalex.org/C11413529 |
| concepts[3].level | 1 |
| concepts[3].score | 0.579507052898407 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[3].display_name | Algorithm |
| concepts[4].id | https://openalex.org/C311688 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5110365152359009 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[4].display_name | Time complexity |
| concepts[5].id | https://openalex.org/C132525143 |
| concepts[5].level | 2 |
| concepts[5].score | 0.2389131486415863 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[5].display_name | Graph |
| concepts[6].id | https://openalex.org/C80444323 |
| concepts[6].level | 1 |
| concepts[6].score | 0.23278877139091492 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[6].display_name | Theoretical computer science |
| concepts[7].id | https://openalex.org/C162324750 |
| concepts[7].level | 0 |
| concepts[7].score | 0.0 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q8134 |
| concepts[7].display_name | Economics |
| concepts[8].id | https://openalex.org/C10138342 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q43015 |
| concepts[8].display_name | Finance |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.8319384455680847 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/vertex |
| keywords[1].score | 0.6753331422805786 |
| keywords[1].display_name | Vertex (graph theory) |
| keywords[2].id | https://openalex.org/keywords/carry |
| keywords[2].score | 0.6054471135139465 |
| keywords[2].display_name | Carry (investment) |
| keywords[3].id | https://openalex.org/keywords/algorithm |
| keywords[3].score | 0.579507052898407 |
| keywords[3].display_name | Algorithm |
| keywords[4].id | https://openalex.org/keywords/time-complexity |
| keywords[4].score | 0.5110365152359009 |
| keywords[4].display_name | Time complexity |
| keywords[5].id | https://openalex.org/keywords/graph |
| keywords[5].score | 0.2389131486415863 |
| keywords[5].display_name | Graph |
| keywords[6].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[6].score | 0.23278877139091492 |
| keywords[6].display_name | Theoretical computer science |
| language | en |
| locations[0].id | doi:10.5539/cis.v14n1p8 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S2764452479 |
| locations[0].source.issn | 1913-8989, 1913-8997 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1913-8989 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Computer and Information Science |
| locations[0].source.host_organization | https://openalex.org/P4310322531 |
| locations[0].source.host_organization_name | Canadian Center of Science and Education |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310322531 |
| locations[0].source.host_organization_lineage_names | Canadian Center of Science and Education |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Computer and Information Science |
| locations[0].landing_page_url | https://doi.org/10.5539/cis.v14n1p8 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5091329448 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-1305-6815 |
| authorships[0].author.display_name | Yijie Han |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I75421653 |
| authorships[0].affiliations[0].raw_affiliation_string | School of Computing and Engineering, University of Missouri at Kansas City, USA |
| authorships[0].institutions[0].id | https://openalex.org/I75421653 |
| authorships[0].institutions[0].ror | https://ror.org/01w0d5g70 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I75421653 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | University of Missouri–Kansas City |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Yijie Han |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | School of Computing and Engineering, University of Missouri at Kansas City, USA |
| authorships[1].author.id | https://openalex.org/A5100722234 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-8772-9627 |
| authorships[1].author.display_name | Chen Sun |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I75421653 |
| authorships[1].affiliations[0].raw_affiliation_string | School of Computing and Engineering, University of Missouri at Kansas City, USA |
| authorships[1].institutions[0].id | https://openalex.org/I75421653 |
| authorships[1].institutions[0].ror | https://ror.org/01w0d5g70 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I75421653 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | University of Missouri–Kansas City |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Chen Sun |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | School of Computing and Engineering, University of Missouri at Kansas City, USA |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014 |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | An O(nlogn/logw) Time Algorithm for Ridesharing |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T11942 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9998999834060669 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2203 |
| primary_topic.subfield.display_name | Automotive Engineering |
| primary_topic.display_name | Transportation and Mobility Innovations |
| related_works | https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2793180915, https://openalex.org/W2386495035, https://openalex.org/W1582047458, https://openalex.org/W1490628945, https://openalex.org/W1514266315, https://openalex.org/W2071291085, https://openalex.org/W2034928178, https://openalex.org/W2051487156 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.5539/cis.v14n1p8 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S2764452479 |
| best_oa_location.source.issn | 1913-8989, 1913-8997 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1913-8989 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Computer and Information Science |
| best_oa_location.source.host_organization | https://openalex.org/P4310322531 |
| best_oa_location.source.host_organization_name | Canadian Center of Science and Education |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310322531 |
| best_oa_location.source.host_organization_lineage_names | Canadian Center of Science and Education |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Computer and Information Science |
| best_oa_location.landing_page_url | https://doi.org/10.5539/cis.v14n1p8 |
| primary_location.id | doi:10.5539/cis.v14n1p8 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S2764452479 |
| primary_location.source.issn | 1913-8989, 1913-8997 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1913-8989 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Computer and Information Science |
| primary_location.source.host_organization | https://openalex.org/P4310322531 |
| primary_location.source.host_organization_name | Canadian Center of Science and Education |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310322531 |
| primary_location.source.host_organization_lineage_names | Canadian Center of Science and Education |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Computer and Information Science |
| primary_location.landing_page_url | https://doi.org/10.5539/cis.v14n1p8 |
| publication_date | 2021-01-08 |
| publication_year | 2021 |
| referenced_works | https://openalex.org/W2565919573, https://openalex.org/W2145569785, https://openalex.org/W2955827721, https://openalex.org/W2752899829, https://openalex.org/W2769413113, https://openalex.org/W2023274209, https://openalex.org/W2061705660, https://openalex.org/W4246219036 |
| referenced_works_count | 8 |
| abstract_inverted_index.a | 52 |
| abstract_inverted_index.w | 75 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.an | 66 |
| abstract_inverted_index.at | 86 |
| abstract_inverted_index.in | 81 |
| abstract_inverted_index.is | 21, 42, 51, 57, 76, 85 |
| abstract_inverted_index.of | 16, 26, 39, 61 |
| abstract_inverted_index.to | 22, 29, 33 |
| abstract_inverted_index.we | 64 |
| abstract_inverted_index.For | 44 |
| abstract_inverted_index.The | 14, 36 |
| abstract_inverted_index.all | 31 |
| abstract_inverted_index.and | 54, 84 |
| abstract_inverted_index.for | 70, 92 |
| abstract_inverted_index.the | 1, 18, 24, 34, 45, 49, 55, 58, 62, 71, 77, 82 |
| abstract_inverted_index.case | 38, 47, 94 |
| abstract_inverted_index.have | 11 |
| abstract_inverted_index.load | 32 |
| abstract_inverted_index.they | 10 |
| abstract_inverted_index.this | 93 |
| abstract_inverted_index.time | 68 |
| abstract_inverted_index.used | 80 |
| abstract_inverted_index.word | 78 |
| abstract_inverted_index.carry | 30 |
| abstract_inverted_index.chain | 53 |
| abstract_inverted_index.least | 87 |
| abstract_inverted_index.logn. | 88 |
| abstract_inverted_index.share | 6 |
| abstract_inverted_index.time. | 97 |
| abstract_inverted_index.where | 48, 74 |
| abstract_inverted_index.chain, | 63 |
| abstract_inverted_index.length | 79 |
| abstract_inverted_index.needed | 28 |
| abstract_inverted_index.number | 25 |
| abstract_inverted_index.people | 5 |
| abstract_inverted_index.vertex | 60 |
| abstract_inverted_index.because | 9 |
| abstract_inverted_index.drivers | 27 |
| abstract_inverted_index.general | 37 |
| abstract_inverted_index.network | 50 |
| abstract_inverted_index.present | 65 |
| abstract_inverted_index.private | 7 |
| abstract_inverted_index.problem | 3, 20, 41 |
| abstract_inverted_index.similar | 12 |
| abstract_inverted_index.solving | 17 |
| abstract_inverted_index.special | 46 |
| abstract_inverted_index.O(nlogn) | 96 |
| abstract_inverted_index.Previous | 89 |
| abstract_inverted_index.achieved | 90 |
| abstract_inverted_index.leftmost | 59 |
| abstract_inverted_index.minimize | 23 |
| abstract_inverted_index.problem, | 73 |
| abstract_inverted_index.requires | 95 |
| abstract_inverted_index.vehicles | 8 |
| abstract_inverted_index.algorithm | 69, 83, 91 |
| abstract_inverted_index.different | 4 |
| abstract_inverted_index.objective | 15 |
| abstract_inverted_index.destination | 56 |
| abstract_inverted_index.ridesharing | 2, 19, 40, 72 |
| abstract_inverted_index.NP-complete. | 43 |
| abstract_inverted_index.destination. | 35 |
| abstract_inverted_index.itineraries. | 13 |
| abstract_inverted_index.O(nlogn/logw) | 67 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.00565185 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |