Estratégias Vencedoras e Complexidade de Jogos de Convexidade em Grafos
Resumo
Segundo Duchet (1987), o primeiro artigo de convexidade em grafos gerais é o artigo de 1981 “Convexity in graphs”. Um dos autores, Frank Harary, introduziu em 1984 os primeiros jogos de convexidade em grafos, na convexidade geodésica, investigados numa sequência de 5 artigos que terminou em 2003. Neste artigo, estendemos esses jogos para outras convexidades e obtemos estratégias vencedoras para geometrias convexas gerais, bem como os primeiros resultados de complexidade PSPACE em jogos de convexidade.Referências
Buckley, F. and Harary, F. (1985). Geodetic games for graphs. Quaestiones Mathematicae, 8:321–334.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic and Discrete Methods, 7(3):433–444.
Gruber, P. M. and Wills, J. M. (1993). Handbook of Convex Geometry. North Holland.
Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Rosenfeld, M. and Zaks, J., editors, Convexity and Graph Theory, volume 87 of North-Holland Mathematics Studies, page 323. North-Holland.
Haynes, T. W., Henning, M. A., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.
Pelayo, I. M. (2013). Geodesic Convexity in Graphs. Springer.
Schaefer, T. J. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.
van de Vel, M. L. J. (1993). Theory of convex structures, volume 50. Elsevier.
Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the Fifth International Congress of Mathematicians, pages 501–504.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic and Discrete Methods, 7(3):433–444.
Gruber, P. M. and Wills, J. M. (1993). Handbook of Convex Geometry. North Holland.
Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Rosenfeld, M. and Zaks, J., editors, Convexity and Graph Theory, volume 87 of North-Holland Mathematics Studies, page 323. North-Holland.
Haynes, T. W., Henning, M. A., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.
Pelayo, I. M. (2013). Geodesic Convexity in Graphs. Springer.
Schaefer, T. J. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.
van de Vel, M. L. J. (1993). Theory of convex structures, volume 50. Elsevier.
Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the Fifth International Congress of Mathematicians, pages 501–504.
Publicado
06/08/2023
Como Citar
ARAÚJO, Samuel N.; FOLZ, Raquel; FREITAS, Rosiane de; BRITO, João Marcos; SAMPAIO, Rudini.
Estratégias Vencedoras e Complexidade de Jogos de Convexidade em Grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 109-113.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230749.
