Catálogo de publicaciones - tesis
Título de Acceso Abierto
Sobre grafos arco-circulares propios y helly
Francisco Juan Soulignac Min Chih Lin
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Un modelo arco-circular es un par M=(C,A) donde C es un círculo y A es una familia de arcos de C. Si ningún arco se encuentra contenido en otro arco entonces decimos que M es propio, mientras que si A satisface la propiedad de Helly entonces decimos que M es Helly. Un grafo G es arco-circular si es el grafo de intersección de los arcos de un modelo arco-circular M. Si además M es propio (resp. Helly) entonces decimos que G es un grafo arco-circular propio (resp. Helly). Los grafos arco-circulares y sus subclases son estudiados con especial atención desde fines de la década de 1960, y al día de hoy la literatura al respecto es muy vasta. Esto se debe a la gran cantidad de aplicaciones que poseen en áreas tan diversas como las bases de datos, la genética, la arqueología, la psicología, la economía, etc., y a las propiedades de su estructura combinatoria. El problema de reconocimiento de grafos arco-circulares, y de varias de sus subclases, puede ser resuelto en tiempo lineal. Más aún, un modelo arco-circular puede ser generado en tiempo lineal. En esta tesis estudiamos la clase de grafos arco-circulares desde una perspectiva estructural y algorítmica, concentrándonos principalmente en las subclases de grafos arco-circulares propios y Helly.Palabras clave – provistas por el repositorio digital
GRAFOS ARCO-CIRCULARES PROPIOS; GRAFOS ARCO-CIRCULARES HELLY; GRAFOS DE INTERVALOS; POTENCIAS DE CAMINOS; POTENCIAS DE CICLOS; ALGORITMOS DE RECONOCIMIENTO; ALGORITMOS DE TRANSFORMACION; ALGORITMOS DE RECONOCIMIENTO DINAMICOS; PROBLEMA DE ISOMORFISMO; GRAFOS CLIQUE; COMPORTAMIENTO DEL OPERADOR CLIQUE ITERADO; PROPER CIRCULAR-ARC GRAPHS; HELLY CIRCULAR-ARC GRAPHS; INTERVAL GRAPHS; POWERS OF PATHS; POWER OF CYCLES; RECOGNITION ALGORITHMS; TRANSFORMATION ALGORITHMS; DYNAMIC RECOGNITION ALGORITHMS; ISOMORPHISM PROBLEM; CLIQUE GRAPHS; K-BEHAVIOR
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2010 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2010
Información sobre licencias CC
