The Gamma Deposition Problem is NP-Complete

  • Marcelo Fonseca Faraj UFMG
  • Sebastián Urrutia UFMG
  • João Fernando Machry Sarubbi CEFET-MG
DOI: https://doi.org/10.5753/etc.2018.3159

Abstract


Gamma Deployment is a metric to evaluate the quality of service in vehicular ad hoc networks (VANETs). Gamma Deployment Problem consists in applying that metric to minimize the amount of RSUs deployed in a VANET. In this work, we present a proof that the that problem is NP-Complete.

References

FARAJ, M. F.; SARUBBI, J. a. F. M.; SILVA, C. M. da; MARTINS, F. V. C. A hybrid genetic algorithm for deploying RSUs in VANETs based on inter-contact time. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. New York, NY, USA: ACM, 2017. (GECCO ’17), p. 193–194. ISBN 978-1-4503-4939-0. Disponível em: [link].

GAREY, M. R.; JOHNSON, D. S. The rectilinear steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, SIAM, v. 32, n. 4, p. 826–834, 1977.

HEATH, L. S. Algorithms for embedding graphs in books. Tese (Doutorado) — University of North Carolina at Chapel Hill, 1985.

SILVA, C. M.; GUIDONI, D. L.; SOUZA, F. S.; PITANGUI, C. G.; SARUBBI, J. F.; PITSILLIDES, A. Gamma deployment: Designing the communication infrastructure in vehicular networks assuring guarantees on the V2I inter-contact time. In: IEEE. Mobile Ad Hoc and Sensor Systems (MASS), 2016 IEEE 13th International Conference on. [S.l.], 2016. p. 263–271.
Published
2018-07-26
How to Cite

Select a Format
FARAJ, Marcelo Fonseca; URRUTIA, Sebastián; SARUBBI, João Fernando Machry. The Gamma Deposition Problem is NP-Complete. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 69-72. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3159.