Um automorfismo de um grafo simples é um isomorfismo dele com ele mesmo, isto é, uma permutação dos vértices que preserva adjacências. O conjunto de todos os automorfismos de um grafo é fechado sob produto e inversão, e portanto é um grupo de permutações.

O problema que consideramos nesta palestra é a determinação do grupo de automorfismos de um grafo simples dado. Este problema generaliza o de determinar se dois grafos são isomorfos, e é relevante para muitos quebra-cabeças como o cubo de Rubik.

Nesta palestra descrevemos o algoritmo de Sims e Schreier para representar de maneira eficiente um grupo de permutações definido por geradores, e como usá-lo para determinar o grupo de automorfismos de um grafo. O algoritmo obviamente é exponencial no pior caso, mas é eficiente na prática para grafos “não perversos”.

Kreweras’ conjecture [G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that any perfect matching of the hypercube $Q_k$ , $k \ge 2$, can be extended to a Hamilton cycle. We prove this conjecture.

Reference(s):
[1] Jiri Fink. Perfect matchings extend to Hamilton cycles in hypercubes. Journal of Combinatorial Theory, series B, 97 (2007), 1074-1076.

In 1996, Matheson and Tarjan conjectured that any n-vertex plane triangulation with n sufficiently large has a dominating set of size at most n/4. We prove this for graphs of maximum degree 6.

Reference(s):
[1] Erika L.C. King a , Michael J. Pelsmajer. Dominating sets in plane triangulations. Discrete Mathematics, 310(17-18):2221-2230.

Let $G$ be a simple graph on $n$ vertices. In this paper, we prove that if $G$ satisfies the condition that $d(x) + d(y) \ge n$ for each $xy \in E(G)$, then $G$ has no nowhere-zero 3-flow if and only if $G$ is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.

Reference(s):
[1] Genghua Fan e Chuixiang Zhou. Degree sum and nowhere-zero 3-flows. Discrete Mathematics, volume 308, Issue 24, 28 December 2008, Pages 6233-6240.

Network Motifs é um assunto que ganhou importância após o pioneiro trabalho de Milo et al (Science 2002). Eles utilizaram motifs para caracterizar redes complexas por meio de seus blocos elementares. Em nosso trabalho, propusemos dois novos algoritmos para calculo de network motifs de tamanho 3 e 4. Os algoritmos são otimizados por meio de cálculos combinatoriais. Os resultados computacionais mostram uma aceleração expressiva no tempo de execução quando comparado a outros programas detectores de motifs disponíveis.

In this talk we discuss a novel branch and bound algorithm based on approximate Binary Decision Diagrams (BDDs). We discuss how approximate BDDs can be used to generate upper and lower bounds for combinatorial optimization problems in the form of relaxation and restriction BDDs. We apply the ideas to the well-studied Maximum Independent Set Problem. Experiments show that the proposed branch and bound algorithm is comparable with state-of-the-art Integer Programing technology on this problem domain.

Joint work with: David Bergman, Willem-Jan van Hoeve and John Hooker.

Richard Feynman triggered the study of Quantum Computing conjecturing that classical computers could not simulate quantum systems efficiently. Since then, quantum computational models have been proposed to study how quantum mechanics influences the power of computing devices. In this work, we study two-way finite automata with quantum and classical states (2QCFA). We systematize previous results on 2QCFAs and show that 2QCFAs can recognize ambiguous context-free languages and also non-context-free languages in polynomial time, extending previous results.