Minimal Spanning Trees with Conflict Graphs
Andreas Darmann (andreas.darmannuni-graz.at)
Abstract: For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges of the original graph. It is shown that the problem becomes strongly NP-hard even if the connected components of the conflict graph consist only of paths of length two. On the other hand, for conflict graphs consisting of disjoint edges (i.e. paths of length one) the problem remains polynomially solvable.
Keywords: minimal spanning tree, conflict graph
Category 1: Combinatorial Optimization (Graphs and Matroids )
Category 2: Network Optimization
Citation: A completely revised and considerably extended paper on this subject is available as Optimization Online 2009-10-2422.
Entry Submitted: 12/19/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|