The minimum spanning tree problem with conflict constraints and its variations

DOI10.1016/J.DISOPT.2010.08.001MaRDI QIDQ429679zbMATH OpenOpenAlexFDO

Authors Ruonan Zhang, Santosh N. Kabadi, 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) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

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

Cites work

• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• scientific article; zbMATH DE number 3894826 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 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
• A tabu thresholding implementation for the irregular stock cutting problem
• Approximating Maximum Clique by Removing Subgraphs
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• Matroid Intersection
• Network flow and 2-satisfiability
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• Tabu Search—Part I
• Tabu Search—Part II
• Tabu Thresholding: Improved Search by Nonmonotonic Trajectories
• The Steiner tree problem
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The traveling salesman problem and its variations
• The volume algorithm: Producing primal solutions with a subgradient method
• Two algorithms for weighted matroid intersection

Cited in

(31)

• 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
• Trees in graphs with conflict edges or forbidden transitions
• 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
• The minimum cost perfect matching problem with conflict pair constraints
• 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
• Paths, trees and matchings under disjunctive constraints
• On conflict-free spanning tree: algorithms and complexity
• The quadratic minimum spanning tree problem and its variations
• The knapsack problem with forfeit sets
• Polyhedral results and stronger Lagrangean bounds for stable spanning trees
• 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
• Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph
• 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)