Passer à la navigation principale Passer à la recherche Passer au contenu principal

Algorithms and formulations for the minimum cut separator problem

  • Normandy University

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

Given G=(V,E) an undirected graph and two specified nonadjacent nodes a and b of V, a cut separator is a subset F=δ(C)⊆E such that a,b∈V\C and a and b belong to different connected components of the graph induced by V\C. Given a nonnegative cost vector c∈R+|E|, cut separator of minimum cost. This new problem is closely related to the vertex separator problem. In this paper, we give a polynomial time algorithm for this problem. We also present four equivalent linear formulations, and we show their tightness. Using these results we obtain an explicit short polyhedral description of the dominant of the cut separator polytope.

langue originaleAnglais
Pages (de - à)977-983
Nombre de pages7
journalElectronic Notes in Discrete Mathematics
Volume36
Numéro de publicationC
Les DOIs
étatPublié - 1 août 2010

Empreinte digitale

Examiner les sujets de recherche de « Algorithms and formulations for the minimum cut separator problem ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation