A note on the problem of r disjoint (s,t)-cuts and some related issues

Walid Ben-Ameur; Mohamed Didi Biha

doi:10.1016/j.orl.2018.03.003

A note on the problem of r disjoint (s,t)-cuts and some related issues

Walid Ben-Ameur
, Mohamed Didi Biha

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider the problem of finding a minimum-cost set of r disjoint (s,t)-cuts. We establish the link between this problem and some of its variations. We give a full description of the dominant of the convex hull of the incidence vectors of sets of r disjoint (s,t)-cuts. This generalizes the well-known result for the r=1 case.

Original language	English
Pages (from-to)	335-338
Number of pages	4
Journal	Operations Research Letters
Volume	46
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2018.03.003
Publication status	Published - 1 May 2018
Externally published	Yes

Keywords

Cut
Graph partitioning
Polyhedra

Access to Document

10.1016/j.orl.2018.03.003

Cite this

@article{48429b8f30ea446789b31bc98b40b42b,

title = "A note on the problem of r disjoint (s,t)-cuts and some related issues",

abstract = "In this paper we consider the problem of finding a minimum-cost set of r disjoint (s,t)-cuts. We establish the link between this problem and some of its variations. We give a full description of the dominant of the convex hull of the incidence vectors of sets of r disjoint (s,t)-cuts. This generalizes the well-known result for the r=1 case.",

keywords = "Cut, Graph partitioning, Polyhedra",

author = "Walid Ben-Ameur and \{Didi Biha\}, Mohamed",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = may,

day = "1",

doi = "10.1016/j.orl.2018.03.003",

language = "English",

volume = "46",

pages = "335--338",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "3",

}

TY - JOUR

T1 - A note on the problem of r disjoint (s,t)-cuts and some related issues

AU - Ben-Ameur, Walid

AU - Didi Biha, Mohamed

PY - 2018/5/1

Y1 - 2018/5/1

N2 - In this paper we consider the problem of finding a minimum-cost set of r disjoint (s,t)-cuts. We establish the link between this problem and some of its variations. We give a full description of the dominant of the convex hull of the incidence vectors of sets of r disjoint (s,t)-cuts. This generalizes the well-known result for the r=1 case.

AB - In this paper we consider the problem of finding a minimum-cost set of r disjoint (s,t)-cuts. We establish the link between this problem and some of its variations. We give a full description of the dominant of the convex hull of the incidence vectors of sets of r disjoint (s,t)-cuts. This generalizes the well-known result for the r=1 case.

KW - Cut

KW - Graph partitioning

KW - Polyhedra

UR - https://www.scopus.com/pages/publications/85044976391

U2 - 10.1016/j.orl.2018.03.003

DO - 10.1016/j.orl.2018.03.003

M3 - Article

AN - SCOPUS:85044976391

SN - 0167-6377

VL - 46

SP - 335

EP - 338

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

A note on the problem of r disjoint (s,t)-cuts and some related issues

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this