Sobre grafos arco-circulares propios y helly

On proper and Helly circular-arc graphs

dc.contributorLin, Min Chih
dc.creatorSoulignac, Francisco Juan
dc.date2010
dc.date.accessioned2017-01-24T19:44:52Z
dc.date.available2017-01-24T19:44:52Z
dc.identifierhttp://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4660_Soulignac
dc.identifierhttp://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=HASH016565719379df94a6511eaa
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/74610
dc.descriptionUn 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.
dc.formattext; pdf
dc.languageInglés
dc.publisherFacultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
dc.subjectComputación / Teoría de Grafos
dc.subjectGRAFOS ARCO-CIRCULARES PROPIOS
dc.subjectGRAFOS ARCO-CIRCULARES HELLY
dc.subjectGRAFOS DE INTERVALOS
dc.subjectPOTENCIAS DE CAMINOS
dc.subjectPOTENCIAS DE CICLOS
dc.subjectALGORITMOS DE RECONOCIMIENTO
dc.subjectALGORITMOS DE TRANSFORMACION
dc.subjectALGORITMOS DE RECONOCIMIENTO DINAMICOS
dc.subjectPROBLEMA DE ISOMORFISMO
dc.subjectGRAFOS CLIQUE
dc.subjectCOMPORTAMIENTO DEL OPERADOR CLIQUE ITERADO
dc.titleSobre grafos arco-circulares propios y helly
dc.titleOn proper and Helly circular-arc graphs
dc.typeTesis


Este ítem pertenece a la siguiente institución