Algorithms for Hamiltonian Paths in Kneser Graphs

  • Andreia Gusmão UFABC
  • Letícia Bueno UFABC
  • Rodrigo Hausen UFABC

Resumo


The Kneser graph K(n, k) has as vertices the k-subsets of the set {1, ...,n} and two vertices are adjacent if the k-subsets are disjoint. The bipartite Kneser graph B(n, k) has as vertices the k and the (n - k)-subsets of {1, ...,n} and two vertices are adjacent if one is a subset of the other. It was proved that a particular hamiltonian path in a reduced graph of B(2k + 1, k) gives a hamiltonian path inK(2k+1, k) and a hamiltonian cycle in B(2k+1, k). We use a structural property in K(2k + 1, k) to devise a parallel algorithm and to improve a known algorithm, both to search for such a particular hamiltonian path in the reduced graph of B(2k + 1, k).

Referências

Bueno, L., Figueiredo, C., Faria, L., Mendonça, C., and Hausen, R. (2011). Hamiltonian cycles in Kneser graphs for n = 2k+2. Electron. Notes Discrete Math., 37(0):291–296. LAGOS’11 – VI Latin-American Algorithms, Graphs and Optimization Symposium.

Bueno, L. R., Faria, L., Figueiredo, C. M. H., and Fonseca, G. D. (2009). Hamiltonian paths in odd graphs. Appl. Anal. Discrete Math., 3(2):386–394.

Chen, Y.-C. (2003). Triangle-free hamiltonian Kneser graphs. J. Combin. Theory Ser. B, 89(1):1–16.

Dejter, I. J. (1985). Graph theory with applications to algorithms and computer science. chapter Hamilton cycles and quotients of bipartite graphs, pages 189–199. John Wiley & Sons, Inc., New York, NY, USA.

Duffus, D. A., Kierstead, H. A., and Snevily, H. S. (1994). An explicit 1-factorization in the middle of the boolean lattice. J. Combin. Theory Ser. A, 65:334–342.

Gusmão, A. C. S. (2013). Um algoritmo paralelo para ciclos hamiltonianos em grafos Kneser. MsC thesis, Universidade Federal do ABC.

Gusmão, A. C. S., Bueno, L. R., and Hausen, R. A. (2013a). Um algoritmo paralelo para o problema de caminhos hamiltonianos em grafos Kneser. In XLV Simpósio Brasileiro de Pesquisa Operacional (SBPO 2013), Natal-RN, pages 3102–3113.

Gusmão, A. C. S., Bueno, L. R., Hausen, R. A., Figueiredo, C. M. H., and Faria, L. (2013b). A note on the middle levels problem. Discrete Appl. Math. Submitted in dez/2013. Preprint available in http://professor.ufabc.edu.br/leticia.bueno/paper.zip.

Johnson, J. R. (2011). An inductive construction for hamilton cycles in Kneser graphs. Electron. J. Combin., 18(1).

Johnson, J. R. and Kierstead, H. A. (2004). Explicit 2-factorisations of the odd graph. Order, 21:19–27.

Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.

Pósa, L. (1976). Hamiltonian circuits in random graphs. Discrete Math., 14(4):359 – 364.

Shields, I. and Savage, C. (1999). A Hamilton path heuristic with applications to the middle two levels problem. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 140, pages 161–178.

Shields, I. and Savage, C. D. (2004). A note on Hamilton cycles in Kneser graphs. Bull. Inst. Combin. Appl., 40:13–22.

Shields, I., Shields, B. J., and Savage, C. D. (2009). An update on the middle levels problem. Discrete Math., 309(17):5271–5277.

Shimada, M. and Amano, K. (2011). A note on the middle levels conjecture. CoRR, abs/0912.4564.
Publicado
28/07/2014
Como Citar

Selecione um Formato
GUSMÃO, Andreia; BUENO, Letícia; HAUSEN, Rodrigo. Algorithms for Hamiltonian Paths in Kneser Graphs. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 27. , 2014, Brasília. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2014 . p. 37-42. ISSN 2763-8820.