Algorithms for Hamiltonian Paths in Kneser Graphs
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.
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
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.
