Publications [#323822] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Pan, J; Victor, W, An efficient algorithm for placing electric vehicle charging stations, Leibniz International Proceedings in Informatics, Lipics, vol. 64 (December, 2016), pp. 7.1-7.12, ISBN 9783959770262
    (last updated on 2018/10/14)

    © Pankaj K. Agarwal, Jiangwei Pan, and Will Victor. 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.