Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



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 [doi]
    (last updated on 2018/11/20)

    © 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320