Bicliques, cliques, neighborhoods y la propiedad de Helly

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2006

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

eng

Descripción:

Un grafo es biclique-Helly cuando el conjunto de bicliques verifica la propiedad de Helly. En esta tesis caracterizamos a la familia de grafos biclique-Helly, y presentamos dos algoritmos polinomiales para el problema de reconocimiento. Por otro lado, relacionamos las clases de grafos biclique-Helly, clique-Helly, discos-Helly y vecindad-Helly. Es natural preguntarse si la propiedad de Helly es hereditaria para sub-grafos inducidos. En este caso, nos referimos a los grafos clique-Helly hereditarios, discos-Helly hereditarios, biclique-Helly hereditarios y vecindad-Helly hereditarios, respectivamente. Las primeras dos clases fueron estudiadas en la literatura. En esta tesis, estudiamos las dos clases restantes. Presentamos caracterizaciones que se basan en subgrafos prohibidos. Ya que esta familia de subgrafos prohibidos tiene tamaño fijo, las caracterizaciones mencionadas dan lugar a algoritmos polinomiales de reconocimiento de las clases. Dado un grafo G, la matriz biclique de G es una matriz con valores en el conjunto {0; 1;-1}, donde las columnas y las filas representan los vértices y las bicliques de G, respectivamente, y los valores 1,-1 en una fila correponden a dos vertices adyacentes de una biclique. Es esta tesis, describimos una caracterización de las matrices bicliques, en forma similar a la empleada en la caracterización de las matrices biclique. En esta caracterización, empleamos el concepto de hypergrafos bipartitos-conformal. Por otra parte, consideramos el caso particular de matrices bicliques de grafos bipartidos. Dada una familia de subconjuntos F, el grafo de intersección de F es un grafo cuyos vértices se corresponden con los conjuntos de F, donde dos vértices son adyacentes si los correspondientes conjuntos se intersecan. En esta tesis definimos el grafo biclique de G, KB(G), como el grafo de intersección de la familia de bicliques de un grafo. Un grafo G es grafo biclique si KB(H) = G, para algún grafo H. En esta tesis presentamos una caracterización de los grafos biclique. Dado G, de¯nimos Nc(G) como el grafo de intersección de las vecindades cerradas de G. En esta tesis estudiamos el grafo Nc(G) en relación con la propiedad de Helly. Los grafos perfectos son importantes desde el punto de vista algorítmico. En este trabajo estudiamos los grafos cuyo grafo biclique es perfecto, es decir, grafos KB-perfectos. Damos una caracterización de los grafos KB-perfectos tales que no continenen al grafo P5 como subgrafo inducido.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus