A Simple Linear Time Split Decomposition Algorithm of Undirected Graphs (2009)
Charbit, Pierre, De Montgolfier, Fabien, Raffinot, Mathieu
We revisit the problem of designing a linear time algorithm for undirected graph split decomposition. Although that this problem has already been claimed to be solved in [E. Dahlhaus, FSTTCS, 1994]...
Un vernis de programmation semi-définie. Journée de (2008)
Combinatoire Rhône-alpes, Pierre Charbit, Uy Ux, Uz Uy
Nous présentons quelques applications de la programmation semi-définie. Cette courte introduction est largement basée sur le survey du domaine fait par M. Goemans: ”Semidefinite Programming in...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
A Note On Computing Set Overlap Classes (2007)
Charbit, Pierre, Habib, Michel, Limouzy, Vincent, De Montgolfier, Fabien, Raffinot, Mathieu, Rao, Michaël
Let ${\cal V}$ be a finite set of $n$ elements and ${\cal F}=\{X_1,X_2, >..., X_m\}$ a family of $m$ subsets of ${\cal V}.$ Two sets $X_i$ and $X_j$ of ${\cal F}$ overlap if $X_i \cap X_j \neq...
The Minimum Feedback Arc Set Problem is NP-hard for Tournaments (2007)
Charbit, Pierre, Thomasse, Stephan, Yeo, Anders
Answering a question of Bang-Jensen and Thomassen, we prove that the minimum feedback arc set problem is NP-hard for tournaments.
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2007)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomassé, Stéphan
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F_2)^d, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of...
A Note On Computing Set Overlap Classes (2007)
Charbit, Pierre, Habib, Michel, Limouzy, Vincent, De Montgolfier, Fabien, Raffinot, Mathieu, Rao, Michaël
Let ${\cal V}$ be a finite set of $n$ elements and ${\cal F}=\{X_1,X_2, \ldots , X_m\}$ a family of $m$ subsets of ${\cal V}.$ Two sets $X_i$ and $X_j$ of ${\cal F}$ overlap if $X_i \cap X_j \neq...
A Note On Computing Set Overlap Classes (2007)
Charbit, Pierre, Habib, Michel, Limouzy, Vincent, De Montgolfier, Fabien, Raffinot, Mathieu, Rao, Michaël
Let ${\cal V}$ be a finite set of $n$ elements and ${\cal F}=\{X_1,X_2, \ldots , X_m\}$ a family of $m$ subsets of ${\cal V}.$ Two sets $X_i$ and $X_j$ of ${\cal F}$ overlap if $X_i \cap X_j \neq...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2007)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomassé, Stéphan
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F_2)^d, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of...
The Minimum Feedback Arc Set Problem is NP-hard for Tournaments (2007)
Charbit, Pierre, Thomasse, Stephan, Yeo, Anders
Answering a question of Bang-Jensen and Thomassen, we prove that the minimum feedback arc set problem is NP-hard for tournaments.
Graphs with Large Girth Not Embeddable in the Sphere (2007)
Charbit, Pierre, Thomasse, Stephan
In 1972, M. Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere $S^d$ in such a way that two vertices joined by an edge have distance more than $\sqrt 3$ (i.e. distance...
Graphs with Large Girth Not Embeddable in the Sphere (2007)
Charbit, Pierre, Thomasse, Stephan
In 1972, M. Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere $S^d$ in such a way that two vertices joined by an edge have distance more than $\sqrt 3$ (i.e. distance...
Finding a vector orthogonal to roughly half a collection of vectors (2006)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stefan
11 pages, 16 références bibliographiques
Cyclic Orders: Equivalence and Duality (2005)
Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomass\'{e}s recent proof of Gallai's conjecture. We explore this notion further : we prove that two cyclic orders are...
Cyclic Orders: Equivalence and Duality (2005)
Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomass\'{e}s recent proof of Gallai's conjecture. We explore this notion further : we prove that two cyclic orders are...
Cyclic Orders: Equivalence and Duality (2005)
Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomass\'{e}s recent proof of Gallai's conjecture. We explore this notion further : we prove that two cyclic orders are...
Cyclic Orders: Equivalence and Duality (2005)
Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomass\'{e}s recent proof of Gallai's conjecture. We explore this notion further : we prove that two cyclic orders are...