Local Search Algorithms for the k-Cardinality Tree Problem

  • In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node weighted graphs. This problem has several applications , which justify the need for efficient methods to obtain good solutions. We review existing literature on the problem. Then we prove that under the condition that the graph contains exactly one trough, the problem can be solved in ploynomial time. For the general NP-hard problem we implemented several local search methods to obtain heuristics solutions, which are qualitatively better than solutions found by constructive heuristics and which require significantly less time than needed to obtain optimal solutions. We used the well known concepts of genetic algorithms and tabu search with useful extensions. We show that all the methods find optimal solutions for the class of graphs containing exactly one trough. The general performance of our methods as compared to other heuristics is illustrated by numerical results.

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Verfasserangaben:Christian Blum, Ehrgott Matthias
URN (Permalink):urn:nbn:de:hbz:386-kluedo-4883
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (48)
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:1999
Jahr der Veröffentlichung:1999
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):03.04.2000
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 $