Estratégias vencedoras para jogos de convexidade em grafos
Revista Eletrônica de Iniciação Científica em Computação · 28.06.2024 · 22 · 11-20
DOI: 10.5753/reic.2024.4644 ↗Kurz gefasst
Fachartikel in der Zeitschrift Revista Eletrônica de Iniciação Científica em Computação, online erschienen am 28.06.2024. Verfasst von João Marcos Brito und 1 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).
Abstract (Originalsprache)
Em 1981, foi publicado o primeiro artigo em inglês de convexidade em grafos. Três anos depois, em 1984, um de seus autores, Frank Harary, introduziu os primeiros jogos de convexidade. Apesar de definidos há muito tempo, as últimas pesquisas sobre jogos de convexidade datavam de 2003, com poucos resultados significativos devido a sua dificuldade. Neste trabalho, conseguimos usar a Teoria de Sprague-Grundy para resolver jogos de convexidade em grafos especiais, como árvores. Além disso, provamos que um desses jogos é PSPACE-difícil, o que o coloca um nível de complexidade acima dos problemas NP-difíceis.
Zitieren
APA
Brito, J. M., & Sampaio, R. (2024). Estratégias vencedoras para jogos de convexidade em grafos. Revista Eletrônica de Iniciação Científica em Computação, 22, 11-20. https://doi.org/10.5753/reic.2024.4644
Vancouver
Brito JM, Sampaio R. Estratégias vencedoras para jogos de convexidade em grafos. Revista Eletrônica de Iniciação Científica em Computação. 2024;22:11-20. doi:10.5753/reic.2024.4644
BibTeX
@article{Brito2024,
author = {Brito, João Marcos and Sampaio, Rudini},
title = {Estratégias vencedoras para jogos de convexidade em grafos},
journal = {Revista Eletrônica de Iniciação Científica em Computação},
year = {2024},
volume = {22},
pages = {11--20},
doi = {10.5753/reic.2024.4644}
}
EUVIMED