Hitting Diamonds and Growing Cacti (2009)
Fiorini, Samuel, Joret, Gwenaël, Pietropaoli, Ugo
We consider the following problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. This NP-hard problem belongs to a...
Sorting under Partial Information (without the Ellipsoid Algorithm) (2009)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël, Munro, J. Ian
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and...
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs (2009)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Newman, Ilan, Weimann, Oren
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either...
Irreducible Triangulations are Small (2009)
Joret, Gwenaël, Wood, David R.
A triangulation of a surface is \emph{irreducible} if there is no edge whose contraction produces another triangulation of the surface. We prove that every irreducible triangulation of a surface with...
The maximum number of cliques in a graph embedded in a surface (2009)
Dujmović, Vida, Fijavž, Gašper, Joret, Gwenaël, Wood, David R.
This paper studies the following question: Given a surface $\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\Sigma$? We characterise the...
Stackelberg Network Pricing is Hard to Approximate (2008)
In the Stackelberg Network Pricing problem, one has to assign tariffs to a certain subset of the arcs of a given transportation network. The aim is to maximize the amount paid by the user of the...
An Efficient Algorithm for Partial Order Production (2008)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël M., Munro, J. Ian
We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special...
Doignon, Jean-Paul, Fiorini, Samuel, Joret, Gwenaël
A graph is alpha-critical if its stability number increases whenever an edge is removed from its edge set. The class of alpha-critical graphs has several nice structural properties, most of them...
The Cops and Robber game on graphs with forbidden (induced) subgraphs (2008)
Joret, Gwenaël, Kamiński, Marcin, Theis, Dirk Oliver
The two-player, complete information game of Cops and Robber is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges....
Jean-paul Doignon, Samuel Fiorini, Gwenaël Joret
A graph is α-critical if its stability number increases whenever an edge is removed from its edge set. The class of α-critical graphs has several nice structural properties, most of them related to...
A Note on a Theorem of Sewell and Trotter (2008)
Abstract. Sewell and Trotter proved that every connected α-critical graph that is not isomorphic to K1, K2 or an odd cycle contains a totally odd K4-subdivision. Their theorem implies an interesting...
Noname manuscript No. (will be inserted by the editor) (2008)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
the date of receipt and acceptance should be inserted later Abstract We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy...
Noname manuscript No. (will be inserted by the editor) (2008)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
the date of receipt and acceptance should be inserted later Abstract We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy...
A little note on the Cops & Robber game on graphs embedded in non-orientable surfaces (2008)
Clarke, Nancy E., Fiorini, Samuel, Joret, Gwenaël, Theis, Dirk Oliver
The two-player, complete information game of Cops and Robber is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges....
Minimum Entropy Orientations (2008)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël
We study graph orientations that minimize the entropy of the in-degree sequence. The problem of finding such an orientation is an interesting special case of the minimum entropy set cover problem...
On a Theorem of Sewell and Trotter (2007)
Fiorini, Samuel, Joret, Gwenaël
Sewell and Trotter [J. Combin. Theory Ser. B, 1993] proved that every connected alpha-critical graph that is not isomorphic to K_1, K_2 or an odd cycle contains a totally odd K_4-subdivision. Their...
Entropy and Stability in Graphs (2007)
Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité...
Entropy and Stability in Graphs (2007)
Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité...
Entropy and Stability in Graphs (2007)
Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité...
Entropy and Stability in Graphs (2007)
Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité...
The Stackelberg Minimum Spanning Tree Game (2007)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, ...
We consider a one-round two-player network pricing game, the {\em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Abstract. In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set...