Heuristics for the K-Cardinality Tree and Subgraph Problems

  • In this paper we consider the problem of finding in a given graph a minimal weight subtree of connected subgraph, which has a given number of edges. These NP-hard combinatorial optimization problems have various applications in the oil industry, in facility layout and graph partitioning. We will present different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree. Both the edge- and node weighted case are investigated and extensive numerical results on the behaviour of the heuristics compared to optimal solutions are presented. The best heuristic yielded results within an error margin of less than one percent from optimality for most cases. In a large percentage of tests even optimal solutions have been found.

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Matthias Ehrgott, Horst. W. Hamacher, J. Freitag, F. Maffioli
URN (Permalink):urn:nbn:de:hbz:386-kluedo-4930
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (8)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:1996
Jahr der Veröffentlichung:1996
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):03.04.2000
Freies Schlagwort / Tag:K-cardinality trees
Quelle:Asia Pacific Journal of Operational Research, vol 14, no 1, May 1997
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 $