Resumen
Signed graphs are a particular type of graph, in which the vertices are connected through edges labeled with a positive or negative weight. Given a signed graph, the Minimum Sitting Arrangement (MinSA) problem aims to minimize the total number of errors produced when the graph (named the input graph) is embedded into another graph (named the host graph). An error in this context appears every time that a vertex with two adjacent (one positive and one negative) is embedded in such a way that the adjacent vertex connected with a negative edge is closer than the adjacent vertex connected with a positive edge. The MinSA can be used to model a variety of real-world problems, such as links in online social networks, the location of facilities, or the relationships between a group of people. Previous studies of this problem have been mainly focused on host graphs, whose structure is a path. However, in this research, we compare two variants of the MinSA that differ in the graph used as the host graph (i.e., a path or a cycle). Particularly, we adapted a previous state-of-the-art algorithm for the problem based on Basic Variable Neighborhood Search. The solutions obtained are compared with the solutions provided by a novel Branch & Bound algorithm for small instances. We also analyze the differences found by using non-parametric statistical tests.
Marcos Robles
Estudiante de Doctorado en Inteligencia Artificial
Marcos Robles se graduó en Ingeniería del Software por la Universidad Rey Juan Carlos en 2022. Trabaja aquí como investigador predoctoral centrado en problemas de embebido de grafos.
Sergio Cavero
Doctor en Inteligencia Artificial
Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.