New heuristics for the minimum fundamental cut

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

Authors

• Alexander J. Perez Tchernov
• Anne M. Schwahn

Abstract

Given an undirected connected network and a weight function finding a basis of the cut space with minimum sum of the cut weights is termed Minimum Cut Basis Problem. This problem can be solved, e.g., by the algorithm of Gomory and Hu [GH61]. If, however, fundamentality is required, i.e., the basis is induced by a spanning tree T in G, the problem becomes NP-hard. Theoretical and numerical results on that topic can be found in Bunke et al. [BHMM07] and in Bunke [Bun06]. In the following we present heuristics with complexity O(m log n) and O(mn), where n and m are the numbers of vertices and edges respectively, which obtain upper bounds on the aforementioned problem and in several cases outperform the heuristics of Schwahn [Sch05].

BibTeX

 
@TechReport{ TchernovSchwahn07:Cut, 
   title = { New heuristics for the minimum fundamental cut }, 
   author = { Alexander J. Perez Tchernov and Anne M. Schwahn },     
   series = { Reports in Wirtschaftsmathematik },  
   number = { 112 }, 
   institution = { Technische Universität Kaiserslautern },       
   note = { Available at http://kluedo.ub.uni-kl.de/volltexte/2007/2118/ }, 
   month = jul, 
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.