The minimum spanning tree problem with conflict constraints and its variations

DOI10.1016/j.disopt.2010.08.001zbMath1241.90167OpenAlexW1982713256MaRDI QIDQ429679

Santosh N. Kabadi, Ruonan Zhang, Abraham P. Punnen

Publication date: 20 June 2012

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

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.08.001

zbMATH Keywords

heuristicscombinatorial optimizationminimum spanning treematroid intersectionconflict graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (25)

Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games ⋮ 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 quadratic minimum spanning tree problem and its variations ⋮ The maximum flow problem with disjunctive constraints ⋮ Spanning cactus: complexity and extensions ⋮ Analysis of an approximate greedy algorithm for the maximum edge clique partitioning 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 ⋮ On conflict-free spanning tree: algorithms and complexity ⋮ 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 ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Assignment problem with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ A unifying model for locally constrained spanning tree problems ⋮ The quadratic balanced optimization problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• The Steiner tree problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A surrogate constraint tabu thresholding implementation for the frequency assignment problem
• Network flow and 2-satisfiability
• The volume algorithm: Producing primal solutions with a subgradient method
• The traveling salesman problem and its variations
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• Matroid Intersection
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Two algorithms for weighted matroid intersection
• Tabu Search—Part I
• Tabu Search—Part II
• A tabu thresholding implementation for the irregular stock cutting problem
• Approximating Maximum Clique by Removing Subgraphs
• Tabu Thresholding: Improved Search by Nonmonotonic Trajectories

This page was built for publication: The minimum spanning tree problem with conflict constraints and its variations