This paper discusses the use of a Kernel Search heuristic method to solve the Minimum Spanning Tree Problem with Conflicts (MSTC). MSTC is a challenging variant of the conventional Minimum Spanning Tree Problem, where certain pairs of edges are in conflict and can’t be included in the same spanning tree. This method could be applied to a variety of practical scenarios, such as designing offshore wind farm networks, analyzing road maps with forbidden transitions, or establishing secure communication paths in distributed environments. The approach’s novelty lies in its use of an independent set of the conflict graph within the algorithm.
Publication date: 5 Jan 2024
Project Page: https://arxiv.org/abs/2401.02222v1
Paper: https://arxiv.org/pdf/2401.02222
