Seminar: A Simple Backtracking Algorithm for Solving the Minimum Spanning Tree Problem with Disjunctive Conflict Constraints

SEMINAR 

DEPARTMENT OF INDUSTRIAL ENGINEERING 

A Simple Backtracking Algorithm for Solving the Minimum Spanning Tree Problem with Disjunctive Conflict Constraints

by

Murat Umut İzer,

Gebze Technical University

Abstract:

The Minimum Spanning Tree problem with Disjunctive Conflict Constraints is an NP-hard extension of the classical Minimum Spanning Tree problem in which certain pairs of edges cannot coexist in the spanning tree. Motivated by the combinatorial structure of the problem, we propose a simple exact backtracking algorithm that recursively dives for an optimal conflict-free spanning tree. The method utilizes depth-first search, integrating infeasibility tests, a simple lower bound, and probing. Compared to existing algorithms, our proposed method offers a transparent, easily implementable alternative.

Keywords: Combinatorial Optimization, Minimum Spanning Tree, Disjunctive Conflict Constraints

Short Bio: 

Murat Umut İzer was born in 1988 in İzmir. He obtained his B.Sc. degree in Industrial Engineering from Gazi University in 2010, and he received his M.A. degree in Management Information Systems from Boğaziçi University in 2016. He achieved his PhD degree in February 2025 from Boğaziçi University, Department of Industrial Engineering with thesis titled “Minimum Spanning Tree Problem with Conflict Constraints”, supervised by Prof. Kuban Altınel and co-advisor Prof. Temel Öncan. He currently works as a researcher at Gebze Technical University on a TÜBİTAK project titled “Extensions and Applications of Polyhedral Omega”. His research interests include Combinatorial Optimization, Decision Support Systems, Integer Programming, and Heuristic Methods.

All interested are cordially invited.  

DATE:  March 13, 2026 

TIME:  Friday, 15:00

ROOM: Engineering Building, M3100