Catálogo de publicaciones - tesis

Compartir en
redes sociales

Título de Acceso Abierto

Caracterizaciones estructurales de grafos de intersección

Luciano Norberto Grippo Guillermo Alfredo Durán

publishedVersion.

Resumen/Descripción – provisto por el repositorio digital
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.
Palabras clave – provistas por el repositorio digital

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

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2011 Biblioteca Digital (FCEN-UBA) (SNRD) acceso abierto

Información

Tipo de recurso:

tesis

Idiomas de la publicación

  • español castellano

País de edición

Argentina

Fecha de publicación

Información sobre licencias CC

https://creativecommons.org/licenses/by/2.5/ar/