Algoritmos para compor uma ferramenta web: geração de grafos grades e cordais e solução de conjunto independente, clique e emparelhamento em grafos
Resumo
Neste trabalho, introduzimos, descrevemos e implementamos algoritmos de geração de grafos e solução de problemas clássicos, agregando à plataforma web Graph Problems, para fins didáticos e científicos. Abordamos a geração de grafos cordais, grades e produtos cartesianos, bem como a solução dos problemas da clique máxima, conjunto independente máximo e emparelhamento máximo.
Referências
(2022). Graph problems tool. https://github.com/braully/graph-problems-tool. Acessado em 15 de Agosto de 2022.
Bondy, J. and Murty, U. (2008). Graph theory, 6 springer. Grad. Texts in Math, 244.
da Silva, B. R. (2018). Algoritmos e limites para os números envoltório e de carathéodory na convexidade p3.
da Silva, D. C. (2022). Algoritmos e Implementações em Grafos. https://github.com/DanteCampos/IC_2021-2022_Graphs/. Acessado em 15 de Agosto de 2022.
Halim, S. (2015). Visualgo–visualising data structures and algorithms through animation. Olympiads in informatics, 9:243–245.
Hopcroft, J. E. and Karp, R. M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225–231.
Robson, J. M. (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425–440.
Shoemaker, A. and Vare, S. (2016). Edmonds’ blossom algorithm. CME.
Tarjan, R. E. and Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):566–579.
UnickSoft (2022). Graph online. https://graphonline.ru/en/. Acessado em 15 de Agosto de 2022.
Bondy, J. and Murty, U. (2008). Graph theory, 6 springer. Grad. Texts in Math, 244.
da Silva, B. R. (2018). Algoritmos e limites para os números envoltório e de carathéodory na convexidade p3.
da Silva, D. C. (2022). Algoritmos e Implementações em Grafos. https://github.com/DanteCampos/IC_2021-2022_Graphs/. Acessado em 15 de Agosto de 2022.
Halim, S. (2015). Visualgo–visualising data structures and algorithms through animation. Olympiads in informatics, 9:243–245.
Hopcroft, J. E. and Karp, R. M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225–231.
Robson, J. M. (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425–440.
Shoemaker, A. and Vare, S. (2016). Edmonds’ blossom algorithm. CME.
Tarjan, R. E. and Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):566–579.
UnickSoft (2022). Graph online. https://graphonline.ru/en/. Acessado em 15 de Agosto de 2022.
Publicado
25/10/2022
Como Citar
DA SILVA, Daniel Campos; DA SILVA, Hebert Coelho.
Algoritmos para compor uma ferramenta web: geração de grafos grades e cordais e solução de conjunto independente, clique e emparelhamento em grafos. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 10. , 2022, Goiás.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 118-129.
DOI: https://doi.org/10.5753/erigo.2022.227410.
