1. RODNA
  2. FCEN
  3. FCEN - Facultad de Ciencias Exactas y Naturales. UBA
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.provenanceFacultad de Ciencias Exactas y Naturales de la UBA-
dc.contributorLin, Min Chih-
dc.contributorSoulignac, Francisco Juan-
dc.creatorSoulignac, Francisco Juan-
dc.date.accessioned2018-05-04T21:59:24Z-
dc.date.accessioned2018-05-28T16:47:17Z-
dc.date.available2018-05-04T21:59:24Z-
dc.date.available2018-05-28T16:47:17Z-
dc.date.issued2010-
dc.identifier.urihttp://10.0.0.11:8080/jspui/handle/bnmm/74356-
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.descriptionA circular-arc model M=(C,A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other, then M is a proper circular-arc model, and if A satisfies the Helly Property, then M is a Helly circular-arc model. A graph G is a circular-arc graph if it is the intersection graph of the arcs of a circular-arc model M. If in addition M is a proper (resp. Helly) circular-arc model then G is a proper (resp. Helly) circular-arc graph. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature since the late 1960's. This is because of their applications in areas as diverse as databases, genetics, archeology, psychology, economics, among others, and because of their nice combinatorial structure. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. Moreover, a circular-arc model can be obtained within the same amount of time. In this thesis we study circular-arc graphs from a structural and algorithmic point of view, with our focus on the proper and Helly subclasses.-
dc.descriptionFil:Soulignac, Francisco Juan. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.-
dc.formatapplication/pdf-
dc.languagespa-
dc.publisherFacultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires-
dc.rightsinfo:eu-repo/semantics/openAccess-
dc.rightshttp://creativecommons.org/licenses/by/2.5/ar-
dc.source.urihttp://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4660_Soulignac-
dc.subjectPROPER CIRCULAR-ARC GRAPHS-
dc.subjectHELLY CIRCULAR-ARC GRAPHS-
dc.subjectINTERVAL GRAPHS-
dc.subjectPOWERS OF PATHS-
dc.subjectPOWER OF CYCLES-
dc.subjectRECOGNITION ALGORITHMS-
dc.subjectTRANSFORMATION ALGORITHMS-
dc.subjectDYNAMIC RECOGNITION ALGORITHMS-
dc.subjectISOMORPHISM PROBLEM-
dc.subjectCLIQUE GRAPHS-
dc.subjectK-BEHAVIOR-
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.typeinfo:eu-repo/semantics/doctoralThesis-
dc.typeinfo:ar-repo/semantics/tesis doctoral-
dc.typeinfo:eu-repo/semantics/publishedVersion-
Aparece en las colecciones: FCEN - Facultad de Ciencias Exactas y Naturales. UBA

Ficheros en este ítem:
No hay ficheros asociados a este ítem.
Mostrar el registro sencillo del ítem