Convergencia y divergencia del grafo biclique iterado

Mostrar todas las versiones(3)

Dado un grafo G, una clique de G es un subgrafo inducido completo maximal, mientras que una biclique de G es un subgrafo inducido bipartito completo maximal de G. El estudio de las bicliques resulta de interés debido a las diferentes aplicaciones en áreas distintas como genética, biología, el estudi...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Montero, Leandro P.
Otros Autores:	Groshaus, Marina
Formato:	Tesis de grado publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2008
Acceso en línea:	https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	seminario:seminario_nCOM000340_Montero
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	Español
orig_language_str_mv	spa
description	Dado un grafo G, una clique de G es un subgrafo inducido completo maximal, mientras que una biclique de G es un subgrafo inducido bipartito completo maximal de G. El estudio de las bicliques resulta de interés debido a las diferentes aplicaciones en áreas distintas como genética, biología, el estudio de redes sociales, inteligencia artificial, etc. Por otro lado, tiene interés a nivel teórico, ya que están estrechamente relacionadas con temas profundamente estudiados como los grafos discos-Helly y los retractos. Dada una familia de conjuntos H, el grafo de intersección de H es el grafo que contiene como conjunto de vértices a los conjuntos de H, y existe una arista entre dos conjuntos E; F ∈ H cuando E y F se intersecan. Los grafos de intersección fueron estudiados en la literatura. Cabe mencionar a los grafos de intervalos (donde H es una familia de intervalos) y al grafo línea (donde H es la familia de aristas de G), entre otros. El grafo clique de G, denotado por K(G), es el grafo de intersección de la familia de cliques de G. Existe un teorema de reconocimiento de grafos clique dado por Roberts y Spencer, pero este no conduce a un algoritmo eficiente para el reconocimiento de dicha clase. En el 2002, se probó que el problema de reconocimiento de grafos clique es NP-completo, es decir, no existe un algoritmo polinomial para resolver este problema (si P 6 ≠ NP). Pensando al grafo clique como un operador, el grafo clique iterado k៱k (G) es el grafo que resulta de aplicar k veces el operador ”grafo clique" al grafo G. El grafo clique iterado fue estudiado ampliamente y pese a no haberse encontrado una caracterización de su comportamiento para un grafo general, se han presentado resultados restringidos a ciertas clases. El grafo biclique de G, KB(G), es el grafo de intersección de las bicliques de G. Este fue definido y caracterizado recientemente. Sin embargo, aún sigue abierta la pregunta sobre la existencia de un algoritmo eficiente que resuelva el problema de reconocimiento de grafos biclique. En este trabajo estudiamos el operador “grafo biclique". Probamos que los únicos posibles comportamientos del grafo biclique iterado son la convergencia y la divergencia, y caracterizamos cada uno de estos. En particular, probamos que un grafo diverge si y solo sí KB(G) contiene a una gema, una casa o k_5 como subgrafos inducidos. Por otro lado, utilizando esta caracterización, presentamos un algoritmo polinomial que resuelve el problema de decidir el comportamiento de un grafo bajo el operador biclique.
author2	Groshaus, Marina
author_facet	Groshaus, Marina Montero, Leandro P.
format	Tesis de grado Tesis de grado publishedVersion
author	Montero, Leandro P.
spellingShingle	Montero, Leandro P. Convergencia y divergencia del grafo biclique iterado
author_sort	Montero, Leandro P.
title	Convergencia y divergencia del grafo biclique iterado
title_short	Convergencia y divergencia del grafo biclique iterado
title_full	Convergencia y divergencia del grafo biclique iterado
title_fullStr	Convergencia y divergencia del grafo biclique iterado
title_full_unstemmed	Convergencia y divergencia del grafo biclique iterado
title_sort	convergencia y divergencia del grafo biclique iterado
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2008
url	https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero
work_keys_str_mv	AT monteroleandrop convergenciaydivergenciadelgrafobicliqueiterado
_version_	1782031580138569728
spelling	seminario:seminario_nCOM000340_Montero2023-09-12T13:13:03Z Convergencia y divergencia del grafo biclique iterado Montero, Leandro P. Groshaus, Marina Dado un grafo G, una clique de G es un subgrafo inducido completo maximal, mientras que una biclique de G es un subgrafo inducido bipartito completo maximal de G. El estudio de las bicliques resulta de interés debido a las diferentes aplicaciones en áreas distintas como genética, biología, el estudio de redes sociales, inteligencia artificial, etc. Por otro lado, tiene interés a nivel teórico, ya que están estrechamente relacionadas con temas profundamente estudiados como los grafos discos-Helly y los retractos. Dada una familia de conjuntos H, el grafo de intersección de H es el grafo que contiene como conjunto de vértices a los conjuntos de H, y existe una arista entre dos conjuntos E; F ∈ H cuando E y F se intersecan. Los grafos de intersección fueron estudiados en la literatura. Cabe mencionar a los grafos de intervalos (donde H es una familia de intervalos) y al grafo línea (donde H es la familia de aristas de G), entre otros. El grafo clique de G, denotado por K(G), es el grafo de intersección de la familia de cliques de G. Existe un teorema de reconocimiento de grafos clique dado por Roberts y Spencer, pero este no conduce a un algoritmo eficiente para el reconocimiento de dicha clase. En el 2002, se probó que el problema de reconocimiento de grafos clique es NP-completo, es decir, no existe un algoritmo polinomial para resolver este problema (si P 6 ≠ NP). Pensando al grafo clique como un operador, el grafo clique iterado k៱k (G) es el grafo que resulta de aplicar k veces el operador ”grafo clique" al grafo G. El grafo clique iterado fue estudiado ampliamente y pese a no haberse encontrado una caracterización de su comportamiento para un grafo general, se han presentado resultados restringidos a ciertas clases. El grafo biclique de G, KB(G), es el grafo de intersección de las bicliques de G. Este fue definido y caracterizado recientemente. Sin embargo, aún sigue abierta la pregunta sobre la existencia de un algoritmo eficiente que resuelva el problema de reconocimiento de grafos biclique. En este trabajo estudiamos el operador “grafo biclique". Probamos que los únicos posibles comportamientos del grafo biclique iterado son la convergencia y la divergencia, y caracterizamos cada uno de estos. En particular, probamos que un grafo diverge si y solo sí KB(G) contiene a una gema, una casa o k_5 como subgrafos inducidos. Por otro lado, utilizando esta caracterización, presentamos un algoritmo polinomial que resuelve el problema de decidir el comportamiento de un grafo bajo el operador biclique. Given a graph G, a clique of G is a maximal complete induced subgraph, while a biclique of G is a maximal bipartite complete induced subgraph. The study of bicliques becomes interesting because of the possible different applications in several areas, such as genetics, biology, social networks, artificial intelligence, etc. Besides they have theoretical interest because of their relationship with some very deeply studied subjects, such as Helly disks and retracts. Given a family of sets H, the intersection graph of H is the graph that has the members of H as vertices, and there is an edge between two sets E; F ∈ H when E and F have non-empty intersection. Intersection graphs have been widely studied in the literature.We can mention as examples,interval graphs (where H is a family of intervales) and line graphs (where H is the family of edges of G), among others. The clique graph of G, denoted by K(G), is the interection graph of the family of cliques of G. There exists a characterization theorem for the clique graphs given by Roberts and Spencer. However, it does not lead to an efficient algorithm for the recognition problem. In 2002, it was proved that the recognition problem for clique graph is NP-Complete. In other words, there is no polynomial algorithm to solve this problem (if P 6≠NP). Considering the clique graph as an operator, the iterated clique graph k៱k (G) is the graph that results of applying k times the \\clique operator" to G. The iterated clique graph has been widely studied. There is no characterization of its behaviour for a general graph, but there are results restricted to some classes. The biclique graph of G, KB(G), is the intersection graph of the bicliques of G. This graph was recently defined and characterized. However, the question of the existence of an efficient algorithm for the recognition of biclique graphs is still an open problem. In this work we study the \\biclique graph" operator. We prove that there are only two possible behaviours of the iterated biclique graph: divergence and convergence, and we characterize each of them. In particular, we prove that a graph diverges if and only if KB(G) contains a gem, a house or K_5 as induced subgraphs. Furthermore, this characterization helped us to derive an algorithm that solves the problem of deciding the behaviour of a graph under the biclique operator in polynomial time. Fil: Montero, Leandro P.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2008-11-25 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000340_Montero

Convergencia y divergencia del grafo biclique iterado

Ejemplares similares