Usando la descomposición de un grafo Halin para el diseño de algoritmos autoestabilizantes

Using Halin graph decomposition for the design of self-stabilizing algorithm

Daniel Uriel Orozco Lomelí (2023, [Tesis de maestría])

Sea G = (V, E) un grafo no dirigido. El problema de encontrar un conjunto independiente fuerte en G, es identificar un conjunto S ⊆ V , tal que dados dos vértices arbitrarios de S, éstos estén separados entre sí por el menos tres aristas. Encontrar un conjunto S de tamaño máximo pertenece a la clase NP-Difícil. Por otro lado, el problema de encontrar un conjunto dominante total en G es identificar un conjunto D ⊆ V , tal que cualquier vértice en V tenga al menos un vecino que pertenezca a D. Encontrar un conjunto D de tamaño mínimo también pertenece a la clase NP-Difícil. En este trabajo de tesis se diseñaron dos algoritmos, uno que resuelve el problema de encontrar un conjunto independiente fuerte maximal y otro que resuelve el problema de encontrar un conjunto dominante total minimal. Estos dos problemas son menos restrictivos que las versiones de optimización descritas al principio de este texto y se sabe que pertenecen a la clase P. Los algoritmos diseñados corren en un sistema distribuido, son autoestabilizantes, son tolerantes a fallas transitorias y funcionan para grafos Halin. Los grafos Halin pertenecen a la clase de grafos 2-outerplanares y tienen la propiedad de que se pueden partir en dos subgrafos muy conocidos, un árbol y un ciclo. Los algoritmos propuestos aprovechan la propiedad anterior para disminuir la complejidad de los mismos. Hasta donde tenemos conocimiento, los algoritmos propuestos, que corren en tiempo lineal en el número de vértices, son los algoritmos más rápidos existentes para los problemas del conjunto independiente fuerte maximal y el conjunto dominante total minimal.

Let G = (V, E) be an undirected graph. The problem of finding a strong stable set in G, is to identify a set S ⊆ V , such that given two arbitrary vertices of S, they are separated from each other by at least three edges. Finding a set S of maximum size belongs to the class NP-Hard. On the other hand, the problem of finding a total dominanting set in G is to identify a set D ⊆ V , such that any vertex in V has at least one neighbor belonging to D. Finding a set D of minimum size also belongs to the class NP-Hard. In this thesis work, two algorithms were designed, one that solves the problem of finding a maximal strong stable set and one that solves the problem of finding a minimal total dominanting set. These two problems are less restrictive than the optimization versions described at the beginning of this text and are known to belong to the P class. The designed algorithms run on a distributed system, are self-stabilizing, are transient fault tolerant, and work for Halin graphs. Halin graphs belong to the 2-outerplanar class of graphs and have the property that they can be split into two well-known subgraphs, a tree and a cycle. The proposed algorithms take advantage of the above property to decrease the complexity of the algorithms. To the best of our knowledge, the proposed algorithms, which run in linear time in the number of vertices, are the fastest existing algorithms for the maximal strong stable set and minimal total dominating set problems.

Grafo Halin, Sistemas Distribuidos, Autoestabilización, Conjunto Independiente Fuerte, Conjunto Dominante Total Halin Graph, Distributed Systems, Self-stabilizing, Strong Stable Set, Total Dominating Set INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES LENGUAJES ALGORÍTMICOS LENGUAJES ALGORÍTMICOS

SOCIO-SPATIAL TRENDS: A GENERAL READING OF PUBLIC SPACE IN HOUSING DEVELOPMENTS

Mariel Organista Camacho Karen Estrella Martínez-Torres Claudia Rivera-Torres (2023, [Artículo, Artículo])

Human nature implies social interaction in diverse environments, where public space, seen as an essential mediator, becomes disconnected, impersonal, and deteriorated exterior spaces, coupled with a lack of interest in participation, inclusion, and personal development. Therefore, this research aimed to analyze the socio-spatial relationships in public spaces based on the inhabitant perception of two housing developments in Ensenada, Baja California, Mexico. This study used a mixed methodological approach to collect information by applying the following instruments: a questionnaire on public spaces, a series of in situ and aerial photographs, and field observations. A total of 196 surveys were applied from 2016 to 2019; the morphological, typological, and functional characteristics of the public space were also observed. The results evidenced an imminent need to carry out their daily activities on a smaller scale and intensity within the housing complex with a level of spatial satisfaction within a scale of 6.37/10. In this regard, the inhabitants reported a higher attendance of the public space use in Los Encinos in contrast to Villas (62.6% and 39.3%, respectively), even though the travel times were shorter in Villas. Regarding the public space usefulness, both cases weighted spatial understanding followed by access ease to the housing complex with a Pearson correlation coefficient equal to or greater than 0.47. In this sense, spatial relations showed dispersion, disorganization, and fragmentation from the ephemeral. In contrast, social relations were considered impersonal, hurried, and of convenience, subordinated to the conditions of the environment, being that personal well-being is built from relations with the exterior and with the collective itself.

Baja California Habitability Public space Social Developments Social-espatial relation conjuntos habitacionales, habitabilidad, Baja California, espacio público, relaciones socioespaciales. HUMANIDADES Y CIENCIAS DE LA CONDUCTA HUMANIDADES Y CIENCIAS DE LA CONDUCTA