Brahim Chaourar

activity

20172019

collaborators

5 papers

cs.DS2019

Connected max cut is polynomial for graphs without $K_{5} \ e$ as a minor

Brahim Chaourar

Given a graph $G = (V, E)$ , a connected cut $δ (U)$ is the set of edges of E linking all vertices of U to all vertices of $V \ U$ such that the induced subgraphs $G [U]$ and $G…

math.CO2019

The facets of the spanning trees polytope

Brahim Chaourar

Let $G = (V, E)$ be an undirected graph. The spanning trees polytope $P (G)$ is the convex hull of the characteristic vectors of all spanning trees of $G$ . In this paper, we describe…

math.OC2019

The Facets of the Subtours Elimination Polytope

Brahim Chaourar

Let $G = (V, E)$ be an undirected graph. The subtours elimination polytope $P (G)$ is the set of $x \in R^{E}$ such that: $0 \leq x (e) \leq 1$ for any edge $e \in E$ , $x (δ (v)) = 2$ f…

cs.DS2018

On the Broadcast Routing Problem in Computer Networks

Brahim Chaourar

Given an undirected graph $G = (V, E)$ , and a vertex $r \in V$ , an $r$ -acyclic orientation of $G$ is an orientation $O E$ of the edges of $G$ such that the digraph $O G = (V, O E)$ is…

cs.CC2017

The Facets of the Bases Polytope of a Matroid and Two Consequences

Brahim Chaourar

Let $M$ to be a matroid defined on a finite set $E$ and $L \subset E$ . $L$ is locked in $M$ if $M ∣ L$ and $M^{*} ∣ (E \ L)$ are 2-connected, and $min\{r(L), r^*(E\backslash L)\}…

Connected max cut is polynomial for graphs without K5​\e as a minor

The facets of the spanning trees polytope

The Facets of the Subtours Elimination Polytope

On the Broadcast Routing Problem in Computer Networks

The Facets of the Bases Polytope of a Matroid and Two Consequences

Connected max cut is polynomial for graphs without $K_{5} \ e$ as a minor