The minimum spanning tree problem with conflict constraints and its variations

DOI10.1016/j.disopt.2010.08.001zbMath1241.90167MaRDI 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

heuristics; combinatorial optimization; minimum spanning tree; matroid intersection; conflict graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

Related Items

On conflict-free spanning tree: algorithms and complexity, The knapsack problem with forfeit sets, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, The maximum flow problem with disjunctive constraints, Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach, The quadratic minimum spanning tree problem and its variations, 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, Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem, Maximum weighted matching with few edge crossings for 2-layered bipartite graph, Approximation of knapsack problems with conflict and forcing graphs, Exact solution algorithms for the maximum flow problem with additional conflict constraints, A unifying model for locally constrained spanning tree problems, Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games, The generalized dependency constrained spanning tree problem, Set covering problem with conflict constraints, A branch and cut algorithm for minimum spanning trees under conflict constraints, Assignment problem with conflicts, The quadratic balanced optimization problem, Spanning cactus: complexity and extensions, Minimum cost noncrossing flow problem on layered networks

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