Minimum Cut Bases in Undirected Networks

  • Given an undirected, connected 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, the problem can be written as a multiterminal network flow problem and is thus solvable in strongly polynomial time. The complexity of this algorithm improves 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 present heuristics, integer programming formulations and summarize first experiences with numerical tests.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Florentine Bunke, Horst W. Hamacher, Francesco Maffioli, Anne Schwahn
URN:urn:nbn:de:hbz:386-kluedo-14913
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (108)
Document Type:Preprint
Language of publication:English
Year of Completion:2007
Year of first Publication:2007
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2007/04/26
Tag:cut basis problem; graph and network algorithm; integer programming
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011