Tessellations On Graphs: Theory, Algorithms and Complexity

Devido ao avanço tecnológico recente, a computação quântica tem ganhado notoriedade. Neste paradigma, o conceito de passeio quântico é fundamental para o desenvolvimento de algoritmos para computadores quânticos. Dentre os modelos de passeios quânticos existentes, destaca-se o modelo escalonado, proposto por Portugal et al., que inclui o modelo de Szegedy como um caso particular, além de parte do modelo com moeda. O modelo escalonado utiliza o conceito de tesselações em grafos para gerar os operadores quânticos de evolução que regem os movimentos do caminhante sobre o grafo. Tesselações em grafos possuem ainda um interessante valor para teoria de grafos visto que o parâmetro tessellation cover number T(G) se relaciona com diversos outros parâmetros presentes na literatura tais como chromatic number, chromatic index, total chromatic number, independent set number, e clique number. Além disso, os problemas que se relacionam com T(G), tais como t-tessellability, good tesellable recognition, e total good tessellable recognition têm relações profundas com problemas clássicos em teoria dos grafos que envolvem coloração de grafos. Neste trabalho apresentamos resultados em teoria de grafos para os problemas relacionados com tesselações em grafos citados acima, tais como complexidade computacional destes problemas para várias classes de grafos, limites inferior e superior para T(G), e o valor de T(G) para diversas classes de grafos. Além disso, apresentamos um modelo de passeio quântico baseado em total tessellation cover, sendo este pioneiro no uso de vértices e arestas como localidades possíveis para o caminhante, simultaneamente.