Caracterizaciones estructurales de grafos de intersección

Mostrar todas las versiones(3)

En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una fami...

Descripción completa

Detalles Bibliográficos
Autor principal: Grippo, Luciano Norberto
Otros Autores: Durán, Guillermo Alfredo
Formato: Tesis doctoral publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2011
Materias:
GRAFOS ARCO CIRCULARES
GRAFOS CIRCULO
SUBGRAFOS INDUCIDOS PROHIBIDOS
GRAFOS PROBE DE BLOQUES
GRAFOS PROBE CO-BIPARTITOS
GRAFOS PROBE DE INTERVALOS
GRAFOS PROBE DE INTERVALOS UNITARIOS
CIRCULAR-ARC GRAPHS
CIRCLE GRAPHS
FORBIDDEN INDUCED SUBGRAPH
PROBE BLOCK GRAPHS
PROBE CO-BIPARTITE GRAPHS
PROBE INTERVAL GRAPHS
PROBE UNIT INTERVAL GRAPHS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4904_Grippo_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n4904_Grippo_oai
record_format dspace
spelling I28-R145-tesis_n4904_Grippo_oai2024-09-02 Durán, Guillermo Alfredo Grippo, Luciano Norberto 2011 En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos. In this Thesis we study structural characterizations for six classes of graphs, namely circular-arc graphs, circle graphs, probe interval graphs, probe unit interval graphs, probe co-bipartite graphs, and probe block graphs. A circular-arc graph (circle graph) is the intersection graph of a family of arcs (chords) on a circle. Let G be a hereditary class of graphs. A graph is probe G if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a graph belonging to the class G by adding edges with both endpoints in the set of nonprobe vertices. Probe G graphs form a superclass of the class G. Hence, probe interval graphs and probe unit interval graphs are extensions of the classes of interval graphs and unit interval graphs, respectively. We partially characterize circular-arc graphs, circle graphs, probe interval graphs and probe unit interval graphs by forbidden induced subgraphs within certain hereditary families of graphs. Finally, a structural characterization for probe co-bipartite graphs that leads to a polynomial-time recognition algorithm and a complete characterization of probe block graphs by a list of forbidden induced subgraphs are presented. Fil: Grippo, Luciano Norberto. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo eng Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar GRAFOS ARCO CIRCULARES GRAFOS CIRCULO SUBGRAFOS INDUCIDOS PROHIBIDOS GRAFOS PROBE DE BLOQUES GRAFOS PROBE CO-BIPARTITOS GRAFOS PROBE DE INTERVALOS GRAFOS PROBE DE INTERVALOS UNITARIOS CIRCULAR-ARC GRAPHS CIRCLE GRAPHS FORBIDDEN INDUCED SUBGRAPH PROBE BLOCK GRAPHS PROBE CO-BIPARTITE GRAPHS PROBE INTERVAL GRAPHS PROBE UNIT INTERVAL GRAPHS Caracterizaciones estructurales de grafos de intersección Structural characterizations of intersection graphs info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4904_Grippo_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Inglés
orig_language_str_mv eng
topic GRAFOS ARCO CIRCULARES
GRAFOS CIRCULO
SUBGRAFOS INDUCIDOS PROHIBIDOS
GRAFOS PROBE DE BLOQUES
GRAFOS PROBE CO-BIPARTITOS
GRAFOS PROBE DE INTERVALOS
GRAFOS PROBE DE INTERVALOS UNITARIOS
CIRCULAR-ARC GRAPHS
CIRCLE GRAPHS
FORBIDDEN INDUCED SUBGRAPH
PROBE BLOCK GRAPHS
PROBE CO-BIPARTITE GRAPHS
PROBE INTERVAL GRAPHS
PROBE UNIT INTERVAL GRAPHS
spellingShingle GRAFOS ARCO CIRCULARES
GRAFOS CIRCULO
SUBGRAFOS INDUCIDOS PROHIBIDOS
GRAFOS PROBE DE BLOQUES
GRAFOS PROBE CO-BIPARTITOS
GRAFOS PROBE DE INTERVALOS
GRAFOS PROBE DE INTERVALOS UNITARIOS
CIRCULAR-ARC GRAPHS
CIRCLE GRAPHS
FORBIDDEN INDUCED SUBGRAPH
PROBE BLOCK GRAPHS
PROBE CO-BIPARTITE GRAPHS
PROBE INTERVAL GRAPHS
PROBE UNIT INTERVAL GRAPHS
Grippo, Luciano Norberto
Caracterizaciones estructurales de grafos de intersección
topic_facet GRAFOS ARCO CIRCULARES
GRAFOS CIRCULO
SUBGRAFOS INDUCIDOS PROHIBIDOS
GRAFOS PROBE DE BLOQUES
GRAFOS PROBE CO-BIPARTITOS
GRAFOS PROBE DE INTERVALOS
GRAFOS PROBE DE INTERVALOS UNITARIOS
CIRCULAR-ARC GRAPHS
CIRCLE GRAPHS
FORBIDDEN INDUCED SUBGRAPH
PROBE BLOCK GRAPHS
PROBE CO-BIPARTITE GRAPHS
PROBE INTERVAL GRAPHS
PROBE UNIT INTERVAL GRAPHS
description En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.
author2 Durán, Guillermo Alfredo
author_facet Durán, Guillermo Alfredo
Grippo, Luciano Norberto
format Tesis doctoral
Tesis doctoral
publishedVersion
author Grippo, Luciano Norberto
author_sort Grippo, Luciano Norberto
title Caracterizaciones estructurales de grafos de intersección
title_short Caracterizaciones estructurales de grafos de intersección
title_full Caracterizaciones estructurales de grafos de intersección
title_fullStr Caracterizaciones estructurales de grafos de intersección
title_full_unstemmed Caracterizaciones estructurales de grafos de intersección
title_sort caracterizaciones estructurales de grafos de intersección
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2011
url https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4904_Grippo_oai
work_keys_str_mv AT grippolucianonorberto caracterizacionesestructuralesdegrafosdeinterseccion
AT grippolucianonorberto structuralcharacterizationsofintersectiongraphs
_version_ 1824354588316139520

Ejemplares similares