Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach

DOI10.1007/s10479-018-2895-yOpenAlexW2806852865MaRDI QIDQ829168

Raffaele Cerulli, Rosa Pentangelo, Andrea Raiconi, Francesco Carrabs

Publication date: 5 May 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-018-2895-y

zbMATH Keywords

minimum spanning treebranch-and-cutconflicting edges

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (7)

Minimum cost flow problem with conflicts ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ The knapsack problem with forfeit sets ⋮ Precedence-constrained arborescences ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ A unifying model for locally constrained spanning tree problems

Cites Work

• The minimum cost perfect matching problem with conflict pair constraints
• The maximum flow problem with disjunctive constraints
• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• Matrices with the Edmonds-Johnson property
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• The Knapsack Problem with Conflict Graphs
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Trees and Cuts

This page was built for publication: Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach