La estructura h-grafo para buscar secuencias maximales de eliminación

FRANCISCO J. SOULIGNAC

Buenos Aires

Congreso; 43 Jornadas Argentinas de Informática JAIIO; 2014

SADIO y Universidad de Palermo

Un problema recurrente en teoría algorítmica de grafos es el de encontrar una secuencia de vertices $v_1, ldots, v_k$ un grafo $G$, de forma tal que $v_i$ satisfaga una propiedad particular $P$ en $G_i = G setminus {v_1, ldots, v_{i-1}}$ para todo $1 leq i leq k$.  La secuencia $v_1, ldots, v_k$ se conoce con el nombre de emph{orden de eliminación $P$}, y es emph{maximal} cuando o bien $k = n$ o bien ningún vértice de $G_{k+1}$ satisface la propiedad $P$. (Como es usual, usamos $n$ y $m$ para denotar la cantidad de vértices y aristas del grafo $G$, respectivamente.)  En el caso particular en que $k = n$, también se dice que $v_1, ldots, v_n$ es un orden emph{perfecto} de eliminación $P$.Muchas clases de grafos interesantes se pueden caracterizar por la existencia de ordenes perfectos de eliminación, considerando distintas propiedades del vertice $v_i$ que es eliminado de $G_i$, e.g.:egin{itemize}  item Grafos cordales: $v_i$ es simplicial en $G_i$,  item Grafos fuertemente cordales: $v_i$ es simple en $G_i$,   item Grafos cop-win: $v_i$ es dominado en $G_i$,  item Grafos bipartitos de eliminación perfecta: $(v_{2i}, v_{2i+1})$ es bisimplicial en $G_{2i}$.end{itemize}En esta charla presento algoritmos para encontrar secuencias maximales de eliminación para las propiedades anteriores: simplicial, simple, dominado, y arista bisimplicial.  Todos los algoritmos funcionan iterativamente, buscando el (o los) siguiente(s) vértice(s) que puede(n) eliminarse de $G_i$.  Se usa una estructura de datos especial para representar a $G_i$, llamada $h$-grafo, que permite la inserción y eliminación de vértices y aristas.  La estructura $h$-grafo es particularmente eficiente cuando cada grafo $G_i$ es ralo.  En esta charla describo someramente la implementación de la estructura $h$-grafo y discuto qué significa que un grafo sea ralo y cómo impactan las distintas nociones de densidad en la complejidad de los algoritmos.