Jack Edmonds
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Jack Edmonds has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Benjamin Lévêque
Laboratoire G-SCOP CNRS 46 Avenue Félix Viallet 38031 Grenoble Cedex France
1 shared publication - Frédéric Maffray
G-SCOP_OC - Optimisation Combinatoire (46 Avenue Félix Viallet 38001 GRENOBLE Cedex 1 - France)
1 shared publication - Kathie Cameron
Department of Mathematics Wilfrid Laurier University Waterloo Ontario Canada
1 shared publication Laura Sanità
Institute of Mathematics, Ecole polytechnique fédérale de Lausanne, Lausanne, Switzerland
1 shared publication- Stéphane Gaubert
INRIA and CMAP École polytechnique Palaiseau France
1 shared publication - Vladimir Gurvich
National Research University Higher School of Economics (HSE)
1 shared publication
Latest Publications
- 1 August 2010
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 36, 1281-1288
Scarf Oiks
- 1 August 2010
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 36, 1281-1288
Scarf Oiks
- 1 August 2010
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 36, 1257-1264
On Finding Another Room-Partitioning of the Vertices
- 1 August 2010
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 36, 1257-1264
On Finding Another Room-Partitioning of the Vertices
- Open Access
Coloring vertices of a graph or finding a Meyniel obstruction
A Meyniel obstruction is an odd cycle with at least five vertices and at most one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as an induced subgraph. Here we give a O(n^2) algorithm that, for any graph, finds either a clique and coloring of the same size or a Meyniel obstruction. We also give a O(n^3) algorithm that, for any graph, finds either aneasily recognizable strong stable set or a Meyniel obstruction.
Open AccessColoring vertices of a graph or finding a Meyniel obstruction
A Meyniel obstruction is an odd cycle with at least five vertices and at most one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as an induced subgraph. Here we give a O(n^2) algorithm that, for any graph, finds either a clique and coloring of the same size or a Meyniel obstruction. We also give a O(n^3) algorithm that, for any graph, finds either aneasily recognizable strong stable set or a Meyniel obstruction.