EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Estratégias vencedoras para jogos de convexidade em grafos

João Marcos Brito, Rudini Sampaio

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →