Registro:
| Documento: | Tesis de Grado |
| Título: | Representaciones minimales de grafos de intervalos unitarios |
| Título alternativo: | Minimal representations of unit interval graphs |
| Autor: | Capillo, Esteban |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2014 |
| Fecha en portada: | 2014 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Soulignac, Francisco Juan |
| Jurado: | De Caria, Pablo Jesús; Groshaus, Marina Esther |
| Idioma: | Inglés |
| Palabras clave: | MODELO DE INTERVALOS UNITARIOS; REPRESENTACION MINIMA; RESTRICCIONES DE SEPARACION; POTENCIA DE CAMINOSUNIT INTERVAL MODEL; MINIMAL REPRESENTATION; SEPARATION CONSTRAINTS; POWERS OF PATHS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000690_Capillo |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000690_Capillo.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000690_Capillo |
| Ubicación: | Dep.COM 000690 |
| 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. Capillo, Esteban. (2014). Representaciones minimales de grafos de intervalos unitarios. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000690_Capillo |
Resumen:
En esta tesis estudiamos el problema de decidir si, dado un modelo de intervalos propios ℒ y una longitud ℓ, existe un modelo de intervalos unitario U de longitud equivalente a ℒ cuyos extremos son enteros y satisfacen ciertas restricciones de separación. Como resultado de esta tesis, diseñamos un algoritmo que encuentra U en tiempo cuadrático, en caso que sea posible. Más aún, cuando dicho modelo unitario no existe, el algoritmo muestra una evidencia de este hecho. Asimismo, mostramos un algoritmo que encuentra el mínimo valor de para el cual el problema tiene solución, que requiere tiempo cuadrático. Por último, mostramos cómo puede aplicarse este algoritmo para encontrar los mínimos k y q tal que el grafo de intersección de I sea un subgrafo inducido de Pkq .
Abstract:
In this thesis we study the problem of deciding if, given a proper interval model ℒ and a length ℓ, there exists a unit interval model U of length equivalent to ℒ whose extremes are integers and such that it satisfies certain separation constraints. Our main result is an algorithm that ends U in quadratic time, when it is possible. Moreover, when such an unit interval model does not exist, the algorithm outputs some evidence about this fact. We also show a quadratic time algorithm that ends the minimum value for which the problem has a solution. Finally, we show how we can apply this algorithm to the minimum k and q such that the intersection graph of I is an induced subgraph of Pkq .
Citación:
---------- APA ----------
Capillo, Esteban. (2014). Representaciones minimales de grafos de intervalos unitarios. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000690_Capillo
---------- CHICAGO ----------
Capillo, Esteban. "Representaciones minimales de grafos de intervalos unitarios". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2014.https://hdl.handle.net/20.500.12110/seminario_nCOM000690_Capillo
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000690_Capillo.pdf
Distrubución geográfica
