Abstract
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
Predoctoral researcher
Marcos Robles graduated in Software Engineering from the Rey Juan Carlos University in 2022. He is working here as a predoctoral researcher focusing in Graph Layout Problems.
Sergio Cavero
Artificial Intelligence Phd Student
Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.