Tesis > Documento


Ver el documento (formato PDF)   Durán, Guillermo Alfredo.  "Sobre grafos intersección de arcos y cuerdas en un círculo"  (2000)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular propios surgen nuevas caracterizaciones para esta subclase y deducimos características de las estructuras prohibidas minimales para arco-circulares. Se estudian todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan, excepto en una de ellas que se demuestra que es vacía. Este resultado asegura que dado un grafo arco-circular propio no unitario, si es clique-Helly debe ser arco-circular Helly. Los grafos circulares son los grafos intersección de cuerdas dentro de un círculo. También aquí presentamos una reseña de los resultados más importantes y definimos las principales subclases, demostrando algunas relaciones de inclusión entre ellas. Damos una condición necesaria para que un grafo sea circular Helly y conjeturamos que también es suficiente. De ser correcta esta conjetura tendríamos una caracterización y también un reconocimiento polinomial para esta subclase. Se muestra como a partir de la mencionada caracterización de Tucker para grafos arco-circular propios y de un teorema de caracterización de Bouchet para los circulares surgen estructuras prohibidas minimales para esta clase. Analizamos también todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan. Estudiamos una superclase de los grafos circulares: los grafos overlap de arcos circulares. Se muestran nuevas propiedades sobre esta clase, poniendo énfasis en su relación con los grafos arco-circulares y los circulares. Damos una condición necesaria para que un grafo sea overlap de arcos circulares. Probarnos la polinomialidad de encontrar una partición en cliques mínima para la clase de grafos que no contienen como subgrafo inducido ciclos inducidos impares de longitud mayor ó igual a 5 ni una rueda de 5 vétices ni un abanico de 5 vértices. Usamos para ello resultados de teoría poliedral para programación lineal entera. Extendemos este mismo resultado para cubrimiento mínimo de cliques por vértices. Aplicamos estos resultados a grafos circular HelIy sin agujeros impares, lo que es interesante pues estos problemas son NP-Hard para la clase general de los grafos y de complejidad desconocida para la clase de los grafos circulares. También demostramos que el problema de cubrimiento mínimo de cliques por vértices es polinomial para grafos arco-circular Helly. Por último, presentamos algunas conclusiones que surgen de este trabajo y las líneas futuras de investigación en estos tópicos, destacando algunos problemas interesantes que permanecen abiertos.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Sobre grafos intersección de arcos y cuerdas en un círculo    
Autor : Durán, Guillermo Alfredo
Director : Szwarcfiter, Jayme L.
Jurados : Meidanis, J.  ; Linhares Sales, C.  ; Gutierrez, M.
Año : 2000
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Grado obtenido : Doctor en Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_3260_Duran
Idioma : Español
Area Temática : Computación / Teoría de Grafos
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34