The minimum spanning tree problem with conflict constraints and its variations

DOI10.1016/J.DISOPT.2010.08.001zbMATH Open1241.90167OpenAlexW1982713256MaRDI QIDQ429679FDOQ429679

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

Recommendations

• Determining a Minimum Spanning Tree with Disjunctive Constraints
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Paths, trees and matchings under disjunctive constraints
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• The quadratic minimum spanning tree problem and its variations

zbMATH Keywords

heuristicscombinatorial optimizationminimum spanning treematroid intersectionconflict graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (27)

• Approximation of knapsack problems with conflict and forcing graphs
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• The generalized dependency constrained spanning tree problem
• The maximum flow problem with disjunctive constraints
• On conflict-free cuts: algorithms and complexity
• Two dependency constrained spanning tree problems
• Set covering problem with conflict constraints
• Minimum cost flow problem with conflicts
• Spanning cactus: complexity and extensions
• Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
• A unifying model for locally constrained spanning tree problems
• Assignment problem with conflicts
• Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• 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 quadratic minimum spanning tree problem and its variations
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• Minimum cost noncrossing flow problem on layered networks
• The Minimum Spanning Tree Problem with Time Window Constraints
• The quadratic balanced optimization problem

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

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