New heuristics for the minimum fundamental cut basis problem

  • 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].

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Alexander J. Perez Tchernov, Anne M. Schwahn
URN (Permalink):urn:nbn:de:hbz:386-kluedo-15041
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (112)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2007
Jahr der Veröffentlichung:2007
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):24.07.2007
Freies Schlagwort / Tag:NP; algorithm ; cut ; data structure ; fundamental cut ; heuristic ; minimum fundamental cut basis
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $