Browsing by Subject "Teoría de grafos"
Now showing items 1-17 of 17
-
(Universidad de Chile, 2019)El k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases de grafos, para intentar resolverlo en ...
-
Algoritmos distribuidos en clases de grafos y un nuevo modelo dinámico de verificación distribuida (Universidad de Chile, 2022)Esta tesis consta de dos partes. En la primera se estudia el problema del cálculo del diámetro en diferentes modelos de computación distribuida. Se inicia por describir un Proof Labeling Scheme (PLS) para resolver el ...
-
(Universidad de Chile, 2020)En esta memoria se enfrentan dos problemas. El primero de ellos es Unsplittable Flow on Trees, en el cual dados un árbol con capacidades G, un conjunto de flujos de distintos tamaños T' y un natural k, se busca encontrar ...
-
(Universidad de Chile, 2022)El presente trabajo define un modelo de subgrafos aleatorios de torneos $T_{p}$ y desarrolla técnicas que combinan ideas de grafos aleatorios, de torneos y de teoría extremal para encontrar ciertas familias de subestructuras ...
-
(Universidad de Chile, 2020)En este trabajo se estudian problemas de coloración en grafos pigmentados. Un grafo pigmentado es una tupla $(G,c)$ con $G$ un grafo y $c:E(G)\to \NN$ una asignación de pigmentos en las aristas. El primer capítulo se centra ...
-
(Universidad de Chile, 2020)En este trabajo se estudia el modelo interactivo de verificación distribuida. En este modelo hay dos entidades: un probador con poder ilimitado, identificado como Merlín, y un verificador distribuido identificado como ...
-
(Universidad de Chile, 2022)La pregunta que dio inicio a esta tesis fue decidir si semigrado mínimo mayor a $\frac k2$ en un grafo orientado garantiza tener como subgrafo a cualquier camino orientado de $k$ aristas. Este enunciado correspondería a ...
-
(Universidad de Chile, 2022)En el presente trabajo se estudian protocolos distribuidos para el reconocimiento de ciertas clases de grafos geométricos. En estos protocolos, existe un probador con poder ilimitado pero no confiable, llamado Merlín, que ...
-
(Universidad de Chile, 2021)En este trabajo, se logró conceptualizar un modelo matemático para resolver el problema del distritaje de códigos postales y la generación de zonas de distribución postal para la Empresa de Correos de Chile. El modelo ...
-
(Universidad de Chile, 2018)The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ ...
-
(Universidad de Chile, 2017)La dependencia de la gente, las empresas y el gobierno con los sistemas de telecomunicaciones se ha vuelto muy fuerte y vital en la mayoría de los casos. Una falla en estos sistemas, como por ejemplo Internet, puede ...
-
(Universidad de Chile, 2021)An automata network (AN) is a network of entities, each holding a state from a finite set and related by a graph structure called an \emph{interaction graph}. Each node evolves according to the states of its neighbors in ...
-
(Universidad de Chile, 2022)El presente trabajo estudia un problema de asignación de clientes a centros de atención: dado un conjunto de clientes en un grafo métrico, y un conjunto de centros en los cuales hay servidores disponibles, se desea asignar ...
-
(Universidad de Chile, 2020)En este trabajo es de interés el estudio de la dinámica simbólica sobre los grupos de Baumslag-Solitar solubles no-abelianos BS(1,N), N>= 2, a través de la comprensión de cómo la estructura de dichos grupos fuerza ...
-
(Universidad de Chile, 2021)Una doble estrella $S(n,m)$ es el grafo obtenido a partir de una estrella con $n$ hojas y otra estrella con $m$ hojas al unir sus centros con una arista. Sea $R(S(n,m))$ el número de Ramsey, definido como el mínimo $N$ tal ...
-
(Universidad de Chile, 2021)En esta tesis se estudia una serie de problemas en combinatoria extremal y probabilista relacionados a árboles y palabras. En la primera parte de este trabajo se estudian qué condiciones debe cumplir un grafo para que ...
-
(Universidad de Chile, 2018)En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, ...
