A branch and cut algorithm for minimum spanning trees under conflict constraints
From MaRDI portal
Publication:2257077
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
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
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