Finding conflict-free minimum weight spanning trees using maximal stable sets of the conflict graph

Umut İzer M., ÖNCAN T., Kuban Altınel İ.

European Journal of Operational Research, 2026 (SCI-Expanded, Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2026
  • Doi Numarası: 10.1016/j.ejor.2026.03.017
  • Dergi Adı: European Journal of Operational Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Compendex, EconLit, INSPEC, MathSciNet, Public Affairs Index, zbMATH
  • Anahtar Kelimeler: Branch-and-bound, Combinatorial optimization, Conflict constraints, Minimum spanning tree problem, Stable set
  • Galatasaray Üniversitesi Adresli: Evet

Özet

Given a connected simple graph with non-negative edge weights and a graph representing conflict relations between the edge pairs, the minimum spanning tree problem with conflict constraints consists of finding a minimum weight spanning tree without any conflicting edge pair. Unlike the ordinary minimum spanning tree problem, this one is known to be NP-hard. We propose a novel branch-and-bound algorithm for the exact solution of the problem. It uses a combinatorial branching rule based on the maximal stable sets of the conflict graph and the information provided by the minimum spanning tree relaxations. According to the results of extensive computational tests, it is possible to say that the new algorithm is very efficient.