Variations of the Minimum Spanning Tree Problem: Algorithmic Approaches and Complexity Study

In a hyperconnected world, designing efficient networks, whether for computers, transportation, or energy, is a fundamental challenge. At the heart of these projects lies the classic Minimum Spanning Tree (MST) problem. But what happens when reality imposes restrictions? What if certain connections cannot coexist or node selection involves incentives? It is in this scenario that this doctoral thesis stands out, offering high-impact contributions to the field of Combinatorial Optimization. The research delves into two complex and NP-hard variations of the MST: the Minimum Conflict-Free Spanning Tree (MCFST) problem and the Prize-Collecting Generalized Minimum Spanning Tree (PCGMST) problem. Going far beyond traditional solutions, this work delivers a comprehensive package that combines cutting-edge theory with efficient algorithms.