Minimum Cut Bases in Undirected Networks

Technical Report, Reports in Wirtschaftsmathematik, Number 108, Technische Universität Kaiserslautern, Available at http://kluedo.ub.uni-kl.de/volltexte/2007/2087/, 2007

Authors

• Florentine Bunke
• Horst W. Hamacher
• Francesco Maffioli
• Anne M. Schwahn

Abstract

Given an undirected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as its graph theoretic counterpart, the cycle basis problem. We consider two versions of the problem, the unconstrained and the fundamental cut basis problem. For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, a polynomial algorithm is presented, which is based on multi-terminal network flow problems. The complexity of the algorithm dominates the complexity of the best algorithms for the cycle basis problem, such that it is preferable for cycle basis problems in planar graphs. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each, from a spanning tree T is shown to be NP-hard. We give an IP formulation and present heuristics for this problem and summarize our experiences with numerical tests.

BibTeX

 
@TechReport{ BunkeEtAl:MinCutBases, 
   title = { Minimum Cut Bases in Undirected Networks }, 
   author = { Florentine Bunke and Horst W. Hamacher and Francesco Maffioli and Anne M. Schwahn },     
   series = { Reports in Wirtschaftsmathematik },  
   number = { 108 }, 
   institution = { Technische Universität Kaiserslautern },       
   note = { Available at http://kluedo.ub.uni-kl.de/volltexte/2007/2087/ },  
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.