Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | computacion |
| Título: | Bicliques, cliques, neighborhoods y la propiedad de Helly |
| Autor: | Groshaus, Marina E. |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la Web: | 2023-05-09 |
| Fecha de defensa: | 2006 |
| Fecha en portada: | 2006 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Szwarcfiter, Jayme L. |
| Idioma: | Inglés |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3998_Groshaus.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n3998_Groshaus |
| Ubicación: | Dep.COM 003998 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Groshaus, Marina E.. (2006). Bicliques, cliques, neighborhoods y la propiedad de Helly. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus |
Resumen:
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.
Abstract:
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.
Citación:
---------- APA ----------
Groshaus, Marina E.. (2006). Bicliques, cliques, neighborhoods y la propiedad de Helly. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus
---------- CHICAGO ----------
Groshaus, Marina E.. "Bicliques, cliques, neighborhoods y la propiedad de Helly". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2006.https://hdl.handle.net/20.500.12110/tesis_n3998_Groshaus
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3998_Groshaus.pdf
