Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | computacion |
| Título: | Sobre grafos intersección de arcos y cuerdas en un círculo |
| Autor: | Durán, Guillermo Alfredo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Departamento de Computación
|
| Publicación en la Web: | 2012-12-14 |
| Fecha de defensa: | 2000 |
| Fecha en portada: | 2000 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor en Ciencias de la Computación |
| Director: | Szwarcfiter, Jayme L. |
| Jurado: | Meidanis, J.; Linhares Sales, C.; Gutierrez, M. |
| Idioma: | Español |
| Tema: | computación/teoría de grafos
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n3260_Duran |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3260_Duran.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n3260_Duran |
| Ubicación: | Dep.003260 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Durán, Guillermo Alfredo. (2000). Sobre grafos intersección de arcos y cuerdas en un círculo. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n3260_Duran |
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.
Citación:
---------- APA ----------
Durán, Guillermo Alfredo. (2000). Sobre grafos intersección de arcos y cuerdas en un círculo. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n3260_Duran
---------- CHICAGO ----------
Durán, Guillermo Alfredo. "Sobre grafos intersección de arcos y cuerdas en un círculo". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2000.https://hdl.handle.net/20.500.12110/tesis_n3260_Duran
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n3260_Duran.pdf
