Resumen

En esta charla vamos a hablar sobre el trabajo de R.E.Tarjan en "Decomposition by clique separators".

Un separador en un grafo es un conjunto de vértices que, al quitarlo, desconecta el resto del grafo. Un separador clique en un grafo es un separador que es una clique (es decir, induce un subgrafo completo). Encontrar un separador clique en un grafo nos permite descomponerlo en dos (o más) subgrafos. Se pueden encontrar relaciones muy interesantes entre las propiedades del grafo original y las de su descomposición, lo que nos permite, por ejemplo, reconstruir parámetros del grafo original sabiendo el valor de los parámetros en los subgrafos en los que lo descompusimos.

En esta charla vamos a definir qué es la descomposición por separadores cliques de un grafo, mencionaremos algunas de las propiedades que esta preserva y presentaremos un algoritmo para calcular dicha descomposición.