Registro:
| Documento: | Tesis Doctoral |
| Título: | Representación numérica de modelos arco-circulares propios |
| Título alternativo: | Numerical representation of proper circular-arc models |
| Autor: | Terlisky, Pablo Ezequiel |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Lugar de trabajo: | Universidad de Buenos Aires - CONICET. Instituto de Cálculo (IC)
|
| Fecha de defensa: | 2024-10-01 |
| Fecha en portada: | 2024 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Soulignac, Francisco Juan |
| Consejero: | Lin, Min Chih |
| Jurado: | Grippo, Luciano Norberto; Ferreira da Silva, Ana S.; Faria, Luerbio |
| Idioma: | Español |
| Palabras clave: | MODELOS ARCO-CIRCULARES PROPIOS; MODELOS ARCO-CIRCULARES UNITARIOS; PROBLEMAS DE REPRESENTACION NUMERICA; SISTEMAS DE INECUACIONES LINEALES; TEORIA POLIEDRAL; GRAFOS TOROIDALES; ETIQUETADO POR DISTANCIAS; SEMIORDENESPROPER CIRCULAR-ARC MODELS; UNIT CIRCULAR-ARC MODELS; NUMERICAL REPRESENTATION PROBLEMS; LINEAR SYSTEMS OF INEQUALITIES; POLYHEDRAL THEORY; TOROIDAL GRAPHS; DISTANCE LABELING; SEMIORDERS |
| Formato: | PDF |
| Handle: |
https://hdl.handle.net/20.500.12110/tesis_n7635_Terlisky |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n7635_Terlisky.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n7635_Terlisky |
| Ubicación: | COM 007635 |
| 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. Terlisky, Pablo Ezequiel. (2024). Representación numérica de modelos arco-circulares propios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n7635_Terlisky |
Resumen:
Un modelo arco-circular propio (PCA) es un par M = (C, A), donde C es un círculo con un punto 0 y A es un conjunto de arcos de C donde ningún arco contiene a otro. El modelo M es equivalente a otro modelo PCA M' cuando los extremos de los arcos de M aparecen en el mismo orden que aquellos de los arcos de M' si se recorren sus círculos en sentido horario desde el 0. Si todos los arcos de M tienen longitud l y sus extremos están a distancia al menos 1, entonces M es un modelo (|C|, l)-CA. El problema de representación unitaria (Rep) pregunta si existe un modelo (pc, l)-CA equivalente a un modelo PCA M dado, para algún c y l. En esta Tesis abordamos Rep modelando cada instancia como un sistema de inecuaciones lineales R que tiene un digrafo toroidal S asociado. Así, derivamos un algoritmo certicante para resolver Rep más simple que los conocidos en la literatura. Además, analizando la representación toroidal de S, demostramos que los vértices de la región factible de R son enteros. Este resultado implica la tratabilidad computacional del problema de representación minimal (Min), donde buscamos un modelo (pc, l)-CA equivalente a un modelo de entrada M que minimice c y l. Diseñamos un algoritmo que resuelve Min en tiempo O(n3) y espacio O(n2). Más allá de Min, denimos el problema de representación mínima (IsoMin), donde, dado un modelo PCA M, buscamos un modelo (c, l)-CA U cuyo grafo de intersección sea isomorfo al de M, minimizando c y l. Demostramos que IsoMin está bien denido y que es NP-Completo. Finalmente, estudiamos k-Mult, una generalización de Rep que consiste en determinar si un modelo PCA M es k-multiplicativo. Intuitivamente, tenemos que encontrar un modelo (c, l)-CA tal que al extender q veces la longitud de sus arcos se obtenga un modelo de la q-ésima potencia de M, para todo q < k [fórmulas aproximadas, revisar las mismas en el original].
Abstract:
A proper circular-arc (PCA) model is a pair M (C, A) where C is a circle with a point 0 and A is a set of arcs of C where no arc contains another. The model M' is equivalent to another PCA model M' when the extremes of the arcs of M' appear in the same order as those of the arcs of M if their circles are traversed clockwise from the point 0. If all the arcs of M have length l and their extremes are at a distance of at least 1 from each other, then M is a (|C|, l)-CA model. The numerical representation problem (Rep) asks whether there is a (c, l)-CA model equivalent to a given PCA model M for some values of c and l. In is Thesis we take on Rep by modeling each instance as a linear inequality system R with an assosciated toroidal graph S. We derive a linear certifying algorithm that solves Rep which is simpler than those known in the literature. Moreover, by analyzing the toroidal representation of S, we show that the vertices of the feasible region of R are integral. This result implies the tractability of the minimal representation (Min) problem, where we search for a (c, l)-CA model which is equivalent to an input model M such that c and l are minimized. We desgin an algorithm that solves Min in O(n3) time and O(n2) space. Beyond Min, we dene the minimum representation (IsoMin) problem where, for a given PCA model M, we search for a (c, l)-CA model U whose intersection graph is isomorphic to that of M, minimizing c y l. We show that IsoMin is well-dened and is NP-Complete. Finally, we study k-Mult, which is a generalization of Rep that consists in determining whether a PCA model M is k-multiplicative. Intiutively, we have to nd a (c, l)-CA model such that if we extend the length of its arcs by a factor of q we obtain a model for the q-th power of M, for all q < k [approximate formulas, verify them in the original].
Citación:
---------- APA ----------
Terlisky, Pablo Ezequiel. (2024). Representación numérica de modelos arco-circulares propios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n7635_Terlisky
---------- CHICAGO ----------
Terlisky, Pablo Ezequiel. "Representación numérica de modelos arco-circulares propios". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2024.https://hdl.handle.net/20.500.12110/tesis_n7635_Terlisky
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n7635_Terlisky.pdf
