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

Reconocimiento continuo de la Lengua de Señas Mexicana

Continuous recognition of Mexican Sign Language

Ricardo Fernando Morfín Chávez (2023, [Tesis de maestría])

La Lengua de Señas Mexicana (LSM) es la lengua utilizada por la comunidad Sorda en México, y, a menudo, subestimada y pasada por alto por la comunidad oyente, lo que resulta en la exclusión sistemática de las personas Sordas en diversos aspectos de la vida. Sin embargo, la tecnología puede desempeñar un papel fundamental en acercar a la comunidad Sorda con la comunidad oyente, promoviendo una mayor inclusión y comprensión entre ambas. El objetivo principal de este trabajo es diseñar, implementar y evaluar un sistema de reconocimiento continuo de señas estáticas en LSM mediante, visión por computadora y técnicas de aprendizaje máquina. Se establecieron objetivos específicos, que incluyen la generación de un conjunto de datos de señas estáticas, pertenecientes al alfabeto manual de la LSM, el diseño de un modelo de reconocimiento, y la evaluación del sistema, tanto en la modalidad aislada como en la continua. La metodología involucra dos evaluaciones distintas. La primera se enfoca en el reconocimiento de señas estáticas en el dominio aislado, para ello se capturaron datos de 20 participantes realizando movimientos de la mano en múltiples ángulos. Se evaluaron diversas técnicas de aprendizaje automático, destacando que el enfoque basado en Máquinas de Soporte Vectorial (SVM) obtuvo los mejores resultados (F1-Score promedio del 0.91). La segunda evaluación se concentra en el reconocimiento continuo de señas estáticas, con datos recopilados de seis participantes con diferentes niveles de competencia en LSM, logrando un rendimiento sólido con errores cercanos al 7 %. Además, se evaluó la viabilidad del sistema en aplicaciones de tiempo real, demostrando un excelente desempeño (velocidad promedio de procesamiento de 45 cuadros por segundo). A pesar de los logros alcanzados, es importante reconocer que este proyecto se centró en el reconocimiento continuo de señas estáticas en LSM. Queda pendiente, como un desafío interesante, la exploración del reconocimiento continuo de señas dinámicas en LSM para futuras investigaciones. Se considera esencial explorar enfoques orientados a la escalabilidad y aplicaciones en tiempo real en investigaciones posteriores.

This study focuses on the continuous recognition of static signs in Mexican Sign Language (Lengua de Señas Mexicana (LSM)), the language used by the Deaf community in Mexico. Despite its significance, LSM is often underestimated and overlooked, leading to the systematic exclusion of Deaf individuals in various aspects of life. The primary objective of this work is to design, implement, and evaluate a continuous static sign recognition system in LSM using computer vision and machine learning techniques. Specific goals were established, including the creation of a dataset of static signs belonging to the manual alphabet of LSM, the design of a recognition model, and the evaluation of the system in both isolated and continuous modes. The methodology involves two distinct evaluations. The first one focuses on the recognition of static signs in the isolated domain, for which data from 20 participants performing hand movements at various angles were collected. Various machine learning techniques were evaluated, with the Máquinas de Soporte Vectorial (SVM)-based approach achieving the best results (average F1-Score of 0.91). The second evaluation centers on the continuous recognition of static signs, using data collected from six participants with varying levels of competence in LSM, achieving robust performance with errors close to 7 %. Furthermore, the feasibility of the system in real-time applications was assessed, demonstrating excellent performance (average processing speed of 45 frames per second). Despite the achievements, it is important to recognize that this project focused on continuous recognition of static signs in LSM. It remains an interesting challenge to explore the continuous recognition of dynamic signs in LSM for future research. It is considered essential to explore scalability-oriented approaches and real-time applications in subsequent investigations.

Lengua de Señas Mexicana (LSM), visión por computadora, aprendizaje automático, alfabeto manual de la LSM, reconocimiento automático de señas estáticas, reconocimiento aislado de señas, reconocimiento continuo de señas, aplicacion Mexican Sign Language (LSM), computer vision, machine learning, LSM manual alpahbet, automatic recognition of static signs, isolated sign recognition, continuous sign recognition, real-time aplications INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES ENSEÑANZA CON AYUDA DE ORDENADOR ENSEÑANZA CON AYUDA DE ORDENADOR