Some Complexity Results for k-Cardinality Minimum Cut Problems

  • Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the k-cardinality minimum cut problem. Given an undirected edge-weighted graph the k-cardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the k-cardinality minimum s-t cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Maurizio Bruglieri, Matthias Ehrgott, Horst W. Hamacher
URN (Permalink):urn:nbn:de:hbz:386-kluedo-10788
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (69)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2000
Jahr der Veröffentlichung:2000
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):07.09.2000
Freies Schlagwort / Tag:cardinality constraint combinatorial optimization ; computational complexity; k-cardinality minimum cut
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 $