Name
Abstract | ||
|---|---|---|
Roadside infrastructure can greatly help disseminate data to drivers. In this paper, we study a fundamental problem, i.e., roadside infrastructure planning. We propose a class of algorithms named Tailor to select a minimum number of intersections to install the infrastructure. In the case when the traffic information is not available, we formulate the intersection selection problem, which formally proves its np-completeness, and provide novel heuristics, i.e., the adapted-bipartite-based heuristics (ABS), to solve it, whose worst-case approximation ratio is 4/3. ABS bridges the planar graph and the bipartite graph through topology transformation. With ABS, the approximate solution to all the problems that are NP-hard in a general planar graph but polynomially solvable in a bipartite graph can be efficiently obtained in the planar graph. We also prove that, even with traffic information, the intersection selection problem remains NP-hard. Greedy heuristics is employed to balance the tradeoff between the number of selected intersections and the percentage of reached vehicles. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TVT.2013.2272724 | IEEE T. Vehicular Technology |
Keywords | Field | DocType |
Face,Vehicles,Bipartite graph,Polynomials,Topology,Approximation methods,Redundancy | Graph theory,Computer science,Bipartite graph,Computer network,Intersection graph,Greedy algorithm,Theoretical computer science,Heuristics,Graph bandwidth,Planar graph,Graph (abstract data type),Distributed computing | Journal |
Volume | Issue | ISSN |
63 | 1 | 0018-9545 |
Citations | PageRank | References |
6 | 0.45 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tan Yan | 1 | 295 | 24.12 |
| Wensheng Zhang | 2 | 1415 | 80.30 |
| Guiling Wang | 3 | 573 | 34.93 |
| Yujun Zhang | 4 | 48 | 7.35 |