Estudio del operador biclique aplicado a distintas clases de grafos

Mostrar todas las versiones(3)

Una biclique en un grafo es un subgrafo inducido bipartito completo maximal. El estudio de las bicliques ha recibido mucha atención en los últimos tiempos. 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,...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Puppo, Juan Pablo Damián
Formato:	Tesis Doctoral
Lenguaje:	Español
Publicado:	2018
Materias:	BICLIQUES CORDAL GRAFO BICLIQUE GRAFO CLIQUE PERMUTACION SPLIT BICLIQUE GRAPHS CHORDAL CLIQUE GRAPH PERMUTATION
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n6926_Puppo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:tesis_n6926_Puppo
record_format	dspace
spelling	todo:tesis_n6926_Puppo2023-10-03T13:14:21Z Estudio del operador biclique aplicado a distintas clases de grafos Study of the biclique operator applyed to different graph classes Puppo, Juan Pablo Damián BICLIQUES CORDAL GRAFO BICLIQUE GRAFO CLIQUE PERMUTACION SPLIT BICLIQUES BICLIQUE GRAPHS CHORDAL CLIQUE GRAPH PERMUTATION SPLIT Una biclique en un grafo es un subgrafo inducido bipartito completo maximal. El estudio de las bicliques ha recibido mucha atención en los últimos tiempos. 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 esta tesis estudiamos el problema de reconocimiento de grafos biclique de algunas clases de grafos. Se pretende con esto, acercarse al problema de reconocimiento de grafos biclique en general, encontrando clases donde el problema de decidir si un grafo es grafo biclique sea polinomial o se pueda probar que es NP-completo. Entre otras, en este trabajo estudiamos el operador biclique aplicado a los grafos bipartitos cordales, split y bipartitos de permutación. También estudiamos el problema de reconocimiento de la clase biclique inversa de los grafos completos, es decir, dado un grafo, decidir si su grafo biclique es completo. Cabe mencionar que, dado que la cantidad de bicliques de un grafo puede ser exponencial, no siempre es eficiente construir el grafo biclique para responder esta pregunta. A biclique in a graph is a maximal bipartite complete induced subgraph. The study of bicliques has received a lot of attention in the last years. The biclique graph of G, KB(G), is the intersection graph of the bicliques of G. It was defined and characterized recently. Nevertheless, the time complexity of the recognition problem for biclique graphs is still open. In this work we study the problem of recognizing biclique graphs in several classes of graphs. By finding classes where the problem of deciding if a graph is a biclique graph of the class is polinomially solvable and other properties of biclique graphs, we intend to approach to the solution of the general recognition problem. For example, in this work we study the biclique operator applied to chordal, split and bipartite permutation graphs. We also study the problem of recognizing the biclique inverse class of complete graphs, that is, given a graph, the problem of deciding if its biclique graph is complete. It is worth to mention that given that the quantity of bicliques of a graph can be exponential, it is not always efficient to built a biclique graph to answer this question. Fil: Puppo, Juan Pablo Damián. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2018-11 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n6926_Puppo
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	Español
topic	BICLIQUES CORDAL GRAFO BICLIQUE GRAFO CLIQUE PERMUTACION SPLIT BICLIQUES BICLIQUE GRAPHS CHORDAL CLIQUE GRAPH PERMUTATION SPLIT
spellingShingle	BICLIQUES CORDAL GRAFO BICLIQUE GRAFO CLIQUE PERMUTACION SPLIT BICLIQUES BICLIQUE GRAPHS CHORDAL CLIQUE GRAPH PERMUTATION SPLIT Puppo, Juan Pablo Damián Estudio del operador biclique aplicado a distintas clases de grafos
topic_facet	BICLIQUES CORDAL GRAFO BICLIQUE GRAFO CLIQUE PERMUTACION SPLIT BICLIQUES BICLIQUE GRAPHS CHORDAL CLIQUE GRAPH PERMUTATION SPLIT
description	Una biclique en un grafo es un subgrafo inducido bipartito completo maximal. El estudio de las bicliques ha recibido mucha atención en los últimos tiempos. 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 esta tesis estudiamos el problema de reconocimiento de grafos biclique de algunas clases de grafos. Se pretende con esto, acercarse al problema de reconocimiento de grafos biclique en general, encontrando clases donde el problema de decidir si un grafo es grafo biclique sea polinomial o se pueda probar que es NP-completo. Entre otras, en este trabajo estudiamos el operador biclique aplicado a los grafos bipartitos cordales, split y bipartitos de permutación. También estudiamos el problema de reconocimiento de la clase biclique inversa de los grafos completos, es decir, dado un grafo, decidir si su grafo biclique es completo. Cabe mencionar que, dado que la cantidad de bicliques de un grafo puede ser exponencial, no siempre es eficiente construir el grafo biclique para responder esta pregunta.
format	Tesis Doctoral
author	Puppo, Juan Pablo Damián
author_facet	Puppo, Juan Pablo Damián
author_sort	Puppo, Juan Pablo Damián
title	Estudio del operador biclique aplicado a distintas clases de grafos
title_short	Estudio del operador biclique aplicado a distintas clases de grafos
title_full	Estudio del operador biclique aplicado a distintas clases de grafos
title_fullStr	Estudio del operador biclique aplicado a distintas clases de grafos
title_full_unstemmed	Estudio del operador biclique aplicado a distintas clases de grafos
title_sort	estudio del operador biclique aplicado a distintas clases de grafos
publishDate	2018
url	https://hdl.handle.net/20.500.12110/tesis_n6926_Puppo
work_keys_str_mv	AT puppojuanpablodamian estudiodeloperadorbicliqueaplicadoadistintasclasesdegrafos AT puppojuanpablodamian studyofthebicliqueoperatorapplyedtodifferentgraphclasses
_version_	1782024285073702912

Estudio del operador biclique aplicado a distintas clases de grafos

Ejemplares similares