- | ||||
|
![]()
|
Minimal Spanning Trees with Conflict Graphs
Andreas Darmann (andreas.darmann 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. Download: [PDF] Entry Submitted: 12/19/2008 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |