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

Los seres alados y solares del arte maya en el Norte de Yucatán

Rubén Morante (2023, [Capítulo de libro])

En nuestro trabajo de campo en el norte de Yucatán estudiamos la iconografía de sitios como Chichén Itzá, Ek Balam y Mayapán. En ellos observamos esculturas con gran calidad artística de seres humanos que portan alas y que, por ello, se presentan como seres celestes relacionados con deidades del panteón maya de los periodos Clásico tardío, Clásico terminal y Posclásico temprano. Para esta investigación partimos de un breve contexto etnohistórico, geográfico y arqueológico de otros sitios mayas, del centro y oriente de México, incluyendo imágenes de códices y pinturas que nos hablan del posible significado que las plumas, las alas y las aves tuvieron en Mesoamérica. Procedimos al análisis de las figuras aladas que se presentan en relación con importantes edificios de sitios del norte de Yucatán. La advocación solar que sugieren parece haber sido común y en esta zona, no sólo hablan de los grandes artistas que los esculpieron, sino de un sistema de creencias que pudo emanar de tradiciones mayas muy tempranas, que en el siglo IX d.C. se manifiesta de manera clara mediante un estilo depurado, una maestría técnica y una alta sensibilidad estética.

In our field work in northern Yucatán we studied the iconography of sites such as Chichén Itzá, Ek Balam, and Mayapán. There we saw great artistic quality sculptures of human beings that carry wings, and because of that we think that represented celestial beings related to deities of the Mayan pantheon of Late Classic, Terminal Classic and Early Postclassic periods. In our research we started with reviews of ethnohistorical, geographical and archaeological contexts in other Mayan sites, from central and eastern Mexico, including images from codices and paintings that tell us about the possible meaning of feathers, wings and birds in Mesoamerica. We proceeded analyze winged figures presented in relation to important buildings in northern Yucatán sites. Solar evocation suggested probably was common in this area and, sculptures not only speak about belief systems that could emanate from very early Mayan traditions, but also speak about great artists, that in 9th century AD. clearly manifested it through a refined style, technical mastery and high aesthetic sensitivity.

Arte maya, seres alados, Norte de Yucatán, Chchén Itzá, Ek Balam. Mayan art, feathers and birds, Northern Yucatán. Maya art--Themes, motives. Maya arts--Mexico--Yucatán (State) Maya sculpture--Themes, motives. Maya mythology. Arte maya. Mitología maya. F1435.3.A7 HUMANIDADES Y CIENCIAS DE LA CONDUCTA CIENCIAS DE LAS ARTES Y LAS LETRAS TEORÍA, ANÁLISIS Y CRÍTICA DE LAS BELLAS ARTES

High quality diet improves lipid metabolic profile and breeding performance in the blue-footed booby, a long-lived seabird

ERICK GONZALEZ MEDINA (2018, [Artículo])

Understanding the role of diet in the physiological condition of adults during reproduction and hence its effect on reproductive performance is fundamental to understand reproductive strategies in long-lived animals. In birds, little is known about the influence of the quality of food consumed at the beginning of the reproductive period and its short-term effects on reproductive performance. To assess the role of diet in the physiological condition of female blue-footed booby, Sula nebouxii (BFBO), during reproduction we evaluated whether individual differences in diet (assessed by using δ13C and δ15N values of whole blood from female birds and muscle tissue of the principal prey species) prior to egg laying and during incubation influenced their lipid metabolic profile (measured as triglyceride levels and C:N ratio) and their reproductive performance (defined by laying date, clutch size and hatching success). Females with higher δ15N values in their blood during the courtship and incubation periods had a higher lipid metabolic profile, earlier laying date, greater clutch size (2–3 eggs) and higher hatching success. Females that laid earlier and more eggs (2–3 eggs) consumed more Pacific anchoveta (Cetengraulis mysticetus) and Pacific thread herring (Opisthonema libertate) than did other females. These two prey species also had high amounts of lipids (C:N ratio) and caloric content (Kcal/g fresh weight). The quality of food consumed by females at the beginning of reproduction affected their physiological condition, as well as their short-term reproductive performance. Our work emphasizes the importance of determining the influence of food quality during reproduction to understand the reproductive decisions and consequences in long-lived animals. © 2018 González-Medina et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

nitrogen 15, triacylglycerol, lipid, animal experiment, Article, breeding, carbon nitrogen ratio, clutch size, controlled study, courtship, diet, egg laying, female, food intake, hatching, lipid metabolism, muscle tissue, nonhuman, prey, reproduction CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA CIENCIAS DE LA TIERRA Y DEL ESPACIO OCEANOGRAFÍA OCEANOGRAFÍA