Bicliques, cliques, neighborhoods y la propiedad de Helly

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Groshaus, Marina E.
Formato:	Tesis Doctoral
Lenguaje:	Inglés
Publicado:	2006
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:tesis_n3998_Groshaus
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language	Inglés
orig_language_str_mv	Inglés
description	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.
format	Tesis Doctoral
author	Groshaus, Marina E.
spellingShingle	Groshaus, Marina E. Bicliques, cliques, neighborhoods y la propiedad de Helly
author_facet	Groshaus, Marina E.
author_sort	Groshaus, Marina E.
title	Bicliques, cliques, neighborhoods y la propiedad de Helly
title_short	Bicliques, cliques, neighborhoods y la propiedad de Helly
title_full	Bicliques, cliques, neighborhoods y la propiedad de Helly
title_fullStr	Bicliques, cliques, neighborhoods y la propiedad de Helly
title_full_unstemmed	Bicliques, cliques, neighborhoods y la propiedad de Helly
title_sort	bicliques, cliques, neighborhoods y la propiedad de helly
publishDate	2006
url	https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus
work_keys_str_mv	AT groshausmarinae bicliquescliquesneighborhoodsylapropiedaddehelly
_version_	1807315431042580480
spelling	todo:tesis_n3998_Groshaus2023-10-03T12:45:37Z Bicliques, cliques, neighborhoods y la propiedad de Helly Groshaus, Marina E. 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. A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs. A natural question is to determine for which graphs the corresponding Helly property holds for every induced subgraph. This leads to the classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighborhood-Helly graphs, respectively. The first two of them have already been characterized. In this thesis, we describe characterizations for the remaining ones, by families of forbidden subgraphs. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes. Given a graph G, the biclique matrix of G is a f0; 1;¡1g matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1,-1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization for biclique matrices, in similar terms as those employed in the characteriza- tion of clique matrices. In the characterizations, we employ the concept of bipartite-conformal hypergraphs. The special case of biclique matrices of bipartite graphs is also considered. Given a family of subsets of some set F, the intersection graph of F is a graph having one vertex for each set of F, and two vertices are adjacent whenever their corresponding sets intersect. sIn this thesis we define the biclique graph of G, KB(G), as the intersection graph of the family of all bicliques of G. A graph G is a biclique graph if there exists a graph H such that KB(H) = G. We present a characterization for biclique graph. The special case of biclique graphs of bipartite graphs is also considered. The closed neighborhood graph is the intersection graph of the closed neighborhoods of G. We study closed neighborhood graphs in relation to the Helly property. Perfect graphs are very interesting from an algorithmic point of view. We study the graphs for which the biclique graph is perfect, the KB-perfect graphs. We give a characterization of the of KB-perfect graphs with no induced P5. Fil: Groshaus, Marina E.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 Tesis Doctoral PDF Inglés info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus

Bicliques, cliques, neighborhoods y la propiedad de Helly

Ejemplares similares