Seminario de Grafos

01 Jul, 2024
 Clique Transversal, un problema difícil e interesante (parte 2)

Clique Transversal, un problema difícil e interesante (parte 2)

Seminario de Grafos

  • 4:00 pm - 5:00 pm
  • Sala 2119 - Pabellón 0+infinito
  • Orador/a: Min Chih Lin

Resumen

Un subconjunto de vértices S se llama clique transversal si todo clique (completo maximal) del grafo contiene al menos un vértice de S. El problema consiste en hallar un clique transversal de menor cardinalidad del grafo. 
En estas dos charlas vamos a explicar por qué este problema es particularmente difícil y junto con otro problema llamado conjunto independiente de cliques (encontrar la mayor cantidad de cliques disjuntos de un grafo) definen una clase de grafos hereditaria denominada grafos t-perfectos. Examinamos algunas técnicas para reducir el problema a otros problemas más conocidos como dominación y clique-cover y en algunos casos pueden conducir a algoritmos polinomiales para algunas subclases de grafos. Presentamos también algoritmos para grafos generales. Finalmente, exhibimos algoritmos aproximados para algunas subclases de grafos donde el problema sigue siendo difícil (NP-Hard).

Contacto

Departamento de Matemática
Pabellón I - Ciudad Universitaria
1428 - Buenos Aires REPÚBLICA ARGENTINA

  • dummy+54 (11) 5285-7618

  • dummy secre@dm.uba.ar

Search