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

  • Publication Type: Article / Article
  • Publication Date: 2026
  • Doi Number: 10.1016/j.ejor.2026.03.017
  • Journal Name: European Journal of Operational Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Compendex, EconLit, INSPEC, MathSciNet, Public Affairs Index, zbMATH
  • Keywords: Branch-and-bound, Combinatorial optimization, Conflict constraints, Minimum spanning tree problem, Stable set
  • Galatasaray University Affiliated: Yes

Abstract

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.