Browsing by Author "Matamala Vásquez, Martín"
Now showing items 1-20 of 48
-
(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 ...
-
(ELSEVIER, 1997-06-10)In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the ...
-
(Universidad de Chile, 2018)Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e ...
-
(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, 2011)Encontrar buenas cotas inferiores y condiciones necesarias para nociones de complejidad y universalidad es uno de los mayores desafíos en el área de la informática teórica. En este sentido, la teoría de la complejidad ...
-
(Elsevier, 2016)A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p >= 1, all partitions of the vertex set of a bipartite graph into p convex sets ...
-
(Universidad de Chile, 2014)La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, ...
-
(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 ...
-
(2004)Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0; : : : ; q−1}. Let s :Q → Q be de0ned by s( ) = ( + 1) mod q, ∀ ∈ Q. In this work we study the following dynamic F on QZ2 . For x ∈ QZ2 ...
-
(Universidad de Chile, 2013)La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz ...
-
(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 ChileCyberDocs, 2010)El tema principal de esta memoria es estudiar características y propiedades de equilibrios, en el contexto de flujos dinámicos en redes. En el caso del modelo de flujo estático, se conocen varios resultados relacionados ...
-
(Universidad de ChileCyberDocs, 2012)
-
(Universidad de Chile, 2014)Se estudia la estructura de grafos completos de tamaño apropiado, con una coloreación de sus aristas en dos colores, de manera tal que no presentan como subgrafos monocromáticos a ciertos tipos de grafos específicos. En ...
-
(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, 2016)El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N candidatos a un puesto de secretaria para ...
-
(Universidad de ChilePrograma Cybertesis, 2008)
-
(Universidad de Chile, 2013)Dos grafos son gemelos si son mutuamente subgrafos entre sí. En grafos finitos la única forma de que dos grafos sean mutuamente subgrafos entre sí es que sean isomorfos. Sin embargo, en grafos infinitos existen grafos que ...
-
(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$ ...
-
(Springer, 2015)An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring of a ...
