O Problema da Deposição Gamma é NP-Completo
Resumo
Deposição Gamma é uma métrica usada para avaliar a qualidade de serviço oferecida por redes veiculares (VANETs). O Problema da Deposição Gamma consiste no emprego dessa métrica na minimização de RSUs para compor VANETs. Neste trabalho, prova-se que esse problema é NP-Completo.
Referências
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.
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.
Publicado
26/07/2018
Como Citar
FARAJ, Marcelo Fonseca; URRUTIA, Sebastián; SARUBBI, João Fernando Machry.
O Problema da Deposição Gamma é NP-Completo. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
