A branch and cut algorithm for minimum spanning trees under conflict constraints

DOI10.1007/s11590-014-0750-xzbMath1308.90033arXiv1307.1424OpenAlexW3104695357MaRDI QIDQ2257077

Phillippe Samer, Sebastián Urrutia

Publication date: 23 February 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.1424

zbMATH Keywords

stable setbranch and cutconflict constraintsoptimal trees

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

Related Items (17)

Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach ⋮ The generalized dependency constrained spanning tree problem ⋮ Set covering problem with conflict constraints ⋮ The rainbow Steiner tree problem ⋮ Minimum cost noncrossing flow problem on layered networks ⋮ Minimum cost flow problem with conflicts ⋮ Two dependency constrained spanning tree problems ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ The knapsack problem with forfeit sets ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ Assignment problem with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem ⋮ A unifying model for locally constrained spanning tree problems ⋮ The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope

Uses Software

• LEMON

Cites Work

• Unnamed Item
• 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
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Matrices with the Edmonds-Johnson property
• Geometric algorithms and combinatorial optimization
• Conflict graphs in solving integer programming problems
• Conflict analysis in mixed integer programming
• The Knapsack Problem with Conflict Graphs
• Disjunctive Programming
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Finding a Maximum Clique in an Arbitrary Graph
• A new approach to the maximum-flow problem
• Covering, Packing and Knapsack Problems
• A tutorial on branch and cut algorithms for the maximum stable set problem
• On the facial structure of set packing polyhedra
• Quadratic bottleneck problems
• Matroids and the greedy algorithm
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: A branch and cut algorithm for minimum spanning trees under conflict constraints