A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs

DOI10.1002/NET.22009MaRDI QIDQ6087142zbMATH OpenFDO

Authors Francesco Carrabs, Manlio Gaudioso

Publication date 11 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/NET.22009

zbMATH Keywords

conflict constraintsconflicting edgesLagrangian approachspanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Polyhedral results and stronger Lagrangean bounds for stable spanning trees
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• A genetic algorithm for minimum conflict weighted spanning tree problem

Cites work

• A branch and cut algorithm for minimum spanning trees under conflict constraints
• A Lagrangean-based decomposition approach for the link constrained Steiner tree problem
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• About Lagrangian methods in integer optimization
• An integer programming model for branching cable layouts in offshore wind farms
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• scientific article; zbMATH DE number 4015993 (Why is no real title available?)
• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• On solving the Lagrangian dual of integer programs via an incremental approach
• Paths, trees and matchings under disjunctive constraints
• The Knapsack Problem with Conflict Graphs
• The maximum flow problem with disjunctive constraints
• The minimum cost perfect matching problem with conflict pair constraints
• The minimum spanning tree problem with conflict constraints and its variations
• The quadratic minimum spanning tree problem and its variations
• Trees in graphs with conflict edges or forbidden transitions
• Truck synchronization at single door cross-docking terminals

Cited in

(10)

• Using Lagrangian dual information to generate degree constrained spanning trees
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Polyhedral results and stronger Lagrangean bounds for stable spanning trees
• Solving the set covering problem with conflicts on sets: a new parallel GRASP
• Extended formulation and branch-and-cut-and-price algorithm for the two connected subgraph problem with disjunctive constraints
• Hybridizing carousel greedy and kernel search: a new approach for the maximum flow problem with conflict constraints
• An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints
• A two-point heuristic to calculate the stepsize in subgradient method with application to a network design problem
• Finding conflict-free minimum weight spanning trees using maximal stable sets of the conflict graph

This page was built for publication: A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087142)