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.
展开▼
机译：由于电动汽车（EV）的日益普及以及道路网络中缺乏充电站的原因，我们研究了最短路径命中率（SPHS）问题。粗略地讲，给定输入图G，目标是计算G顶点的小尺寸子集H，以便通过将充电站放置在H的顶点上，G中的每个最短路径都可以实现EV，即EV可以在G的两个顶点之间以最短路径行进并充满电。在本文中，我们提出了一种双标准逼近算法，该算法的运行时间在G的范围内接近线性，其对数逼近| H |。并可能要求EV偏离最短路径。我们还提出了一种数据结构，用于计算G的两个查询顶点之间的EV可行路径。
展开▼
