2026-07-25T10:29:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6778 2024-03-06T10:38:52Z ddc:004 open_access

An Efficient Algorithm for Placing Electric Vehicle Charging Stations Agarwal, Pankaj K. Pan, Jiangwei Victor, Will Shortest path hitting set Charging station placement Electric vehicle Motivated by the increasing popularity of electric vehicles (EV) and a lack of charging stations in the road network, we study the shortest path hitting set (SPHS) problem. Roughly speaking, given an input graph G, the goal is to compute a small-size subset H of vertices of G such that by placing charging stations at vertices in H, every shortest path in G becomes EV-feasible, i.e., an EV can travel between any two vertices of G through the shortest path with a full charge. In this paper, we propose a bi-criteria approximation algorithm with running time near-linear in the size of G that has a logarithmic approximation on |H| and may require the EV to slightly deviate from the shortest path. We also present a data structure for computing an EV-feasible path between two query vertices of G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Jiangwei Pan and Will Victor 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.7 urn:nbn:de:0030-drops-67782 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode