Aluno: Antonio Marcos Shiro Arnauts Hachisuca
Orientador: Marcel K. de Carli Silva
Em 2009, Nicholas J. A. Harvey propôs um algoritmo probabilístico para resolver o problema do emparelhamento máximo em grafos em tempo O(\(n^\omega\)), onde \(n\) é o número de vértices e \(\omega\) é o menor expoente para o qual existe um algoritmo em tempo O(\(n^\omega\)) para a multiplicação de matrizes. Atualmente, é conhecido que \(\omega < 2.38\). O algoritmo se fundamenta em conceitos da teoria algébrica de grafos para resolver o problema. Sua implementação utiliza atualizações "lazy" e um algoritmo de multiplicação de matrizes em caixa preta. Sua importância é destacada pela resolução de uma pergunta em aberto proposta por Mucha e Sankowski, além de refutar a conjectura da inexistência de algoritmos que empregam estratégias "lazy" para resolver esse problema.
Este trabalho tem como objetivo o estudo e a implementação do algoritmo proposto por Harvey. Vale ressaltar que não será realizada a implementação da multiplicação de matrizes em complexidade sub-cúbica, uma vez que isso foge do escopo deste trabalho.
Inicialmente, planeja-se uma introdução à teoria algébrica de grafos e aos conceitos de álgebra linear relevantes para o algoritmo. Em seguida, pretende-se explicar e provar a corretude do algoritmo. Por fim, será feita a implementação do algoritmo.