The article discusses a new approach to solve the Minimum Spanning Tree Problem with Conflicts (MSTC) using a Kernel Search heuristic method. The MSTC is a variant of the classical Minimum Spanning Tree Problem, where some edges cannot be included in the spanning tree at the same time due to conflict. The authors propose to solve this problem using an independent set of the conflict graph within the algorithm. They test their approach on benchmark instances and compare their results with other heuristics available in the literature. The paper also discusses various practical applications of MSTC in areas like offshore wind farm network design, road map analysis, oil pipeline system installation, and cybersecurity.
Publication date: 5 Jan 2024
Project Page: https://arxiv.org/abs/2401.02222v1
Paper: https://arxiv.org/pdf/2401.02222
