Consortium of Swiss Academic Libraries

Bulk-Robust combinatorial optimization

Adjiashvili, David ; Stiller, Sebastian ; Zenklusen, Rico

In: Mathematical Programming, 2015, vol. 149, no. 1-2, p. 361-390

Université de Fribourg

A 2-approximation for the maximum satisfying bisection problem

Ries, Bernard ; Zenklusen, Rico

In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175

Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...

Université de Fribourg

A note on chromatic properties of threshold graphs

Ries, Bernard ; de Werra, Dominique ; Zenklusen, Rico

In: Discrete Mathematics, 2012, vol. 312, no. 10, p. 1838-1843

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and a...

Université de Fribourg

Blockers and transversals in some subclasses of bipartite graphs : When caterpillars are dancing on a grid

Ries, Bernard ; Bentz, Cédric ; Picouleau, Christophe ; de Werra, Dominique ; Costa, Marie-Christine ; Zenklusen, Rico

In: Discrete Mathematics, 2010, vol. 310, p. 132-146

Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the...

Consortium of Swiss Academic Libraries

New approaches to multi-objective optimization

Grandoni, Fabrizio ; Ravi, R. ; Singh, Mohit ; Zenklusen, Rico

In: Mathematical Programming, 2014, vol. 146, no. 1-2, p. 525-554

Université de Fribourg

Blockers and transversals

Zenklusen, Rico ; Ries, Bernard ; Picouleau, Christophe ; de Werra, Dominique ; Costa, Marie-Christine ; Bentz, Cédric

In: Discrete Mathematics, 2009, vol. 309, p. 4306-4314

Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular...