CI084 / INFO7056

Tópicos em Teoria dos Grafos / Tópicos em Algoritmos

2022/1

Professor: André Guedes

Horário: 3as e 5as, 15:30

Sala de aula: PC-03

Programa

Tópicos em teoria dos grafos enfocando classes de grafos. Apresentarei algumas classes, com caracterizações e algoritmos de reconhecimento, além de exemplos de problemas que, restritos a certas classes de grafos, mudam de classe de complexidade.

Objetivos

Apresentar temas mais avançados em Teoria dos Grafos aos alunos graduação e pós-graduação.

Cálculo da nota

  • Trabalho (texto + apresentação)

Veja as notas aqui!

Calendário

  • 07/06/2022: Início do semestre
  • 14/06/2022: Não teremos aula
  • 14/07/2022: Não teremos aula (viagem)

Bibliografia

  • Brandstädt, A., Bang Le, V., Spinrad, J.P., Graph Classes: A Survey, SIAM, 1999. ISBN 089871432X, 9780898714326.
  • Szwarcfiter J.L., Grafos e Algoritmos Computacionais, Editora Campus, 1988.
  • Szwarcfiter J.L., Teoria Computacional de Grafos, Série SBC, Elsevier, 2018.
  • Harary F., Graph Theory, Perseus, 1969.
  • Bondy, J.A., Murty, U.S.R., Graph Theory with Applications, Elsevier, 1976.

Leitura Complementar

  • A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, Massachusetts, 1983.
  • T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2009.
  • S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, McGraw-Hill, 2006.
  • Edsger Wybe Dijkstra. A Discipline of Programming (1st ed.). Prentice Hall PTR, Upper Saddle River, NJ, USA. 1997.
    1. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.
      1. Knuth, The Art of Computer Programming, Addison-Wesley, 1974.
  • U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
  • R. Sedgewick, Algorithms, Addison-Wesley, Reading, Massachusetts, 1983.
  • Steve S. Skiena, The Algorithm Design Manual, Springer, 1997. ISBN-13: 978-0387948607 ISBN-10: 0387948600 https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/INDEX.HTM
    1. Ziviani, Projeto de Algoritmos, Thompson, segunda edição, 2004
  • Seminário de Jayme Luiz Szwarcfiter (UFRJ e UERJ) em 25/06/2020. Título: Dijkstra Graphs

Artigos

  • Pavol Hell, Jing Huang, Jephian C.-H. Lin, and Ross M. McConnell. Bipartite Analogues of Comparability and Cocomparability Graphs. SIAM Journal on Discrete Mathematics 2020 34:3, 1969-1983. URL: [https://doi.org/10.1137/19M1263789]
  • Frank Harary, Jerald A. Kabell, Frederick R. McMorris. Bipartite intersection graphs. Commentationes Mathematicae Universitatis Carolinae, Vol. 23 (1982), No. 4, 739--745. URL: [http://dml.cz/dmlcz/106192]

URLs

Generated on: 2022-09-25 15:41 UTC.