Publications of Nathann Cohen
BACK TO COATI PUBLICATION INDEX
Publications of Nathann Cohen
-
N. Cohen.
Some results in graph theory and its applications.
PhD thesis,
Ecole doctorale STIC, Université de Nice-Sophia Antipolis,
October 2011.
[WWW
] [Abstract] [bibtex-entry]
-
Thibaud Trolliet,
Nathann Cohen,
Frédéric Giroire,
Luc Hogie,
and Stéphane Pérennes.
Interest clustering coefficient: a new metric for directed networks like Twitter.
Journal of Complex Networks,
2021.
[WWW
] [PDF
]
Keywords:
complex networks,
clustering coefficient,
directed networks,
social networks,
Twitter,
link recommendation.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a Combinatorial Game in Graphs Through Linear Programming.
Algorithmica,
82(2):212-244,
2020.
[WWW
] [PDF
]
Keywords:
Grid,
Tree,
Linear Programming,
Domination,
Graphs,
Spy game,
Cops and Robber games.
[bibtex-entry]
-
Pierre Aboulker,
Nathann Cohen,
Frédéric Havet,
William Lochet,
Phablo F S Moura,
and Stéphan Thomassé.
Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number.
The Electronic Journal of Combinatorics,
26:P3.19,
July 2019.
[WWW
] [PDF
] [bibtex-entry]
-
Julien Bensmail,
Thibaut Blanc,
Nathann Cohen,
Frédéric Havet,
and Leonardo Rocha.
Backbone colouring and algorithms for TDMA scheduling.
Discrete Mathematics and Theoretical Computer Science,
Vol. 21 no. 3(3):#24,
July 2019.
[WWW
] [PDF
]
Keywords:
Wireless networks,
TDMA scheduling,
Backbone colouring,
Algorithmic complexity.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Raul Lopes.
Bispindles in strongly connected digraphs with large chromatic number.
The Electronic Journal of Combinatorics,
June 2018.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
Journal of Graph Theory,
89(4):439-456,
April 2018.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
Dorian Mazauric,
Ignasi Sau,
and Rémi Watrigant.
Complexity dichotomies for the Minimum F -Overlay problem.
Journal of Discrete Algorithms,
52-53:133-142,
September 2018.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen and Frédéric Havet.
On the minimum size of an identifying code over all orientations of a graph.
The Electronic Journal of Combinatorics,
25(1):#P1.49,
2018.
[WWW
] [PDF
]
Keywords:
identifying code,
orientations,
NP-complete.
[bibtex-entry]
-
Nathann Cohen,
Nicolas Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Spy-game on graphs: Complexity and simple topologies.
Theoretical Computer Science,
725:1 - 15,
May 2018.
[WWW
] [PDF
]
Keywords:
Graphs,
Cops and Robber games,
PSPACE-hard.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a Combinatorial Game in Graphs Through Linear Programming.
Algorithmica,
August 2018.
[WWW
] [PDF
]
Keywords:
Domination,
Graphs,
Spy game,
Cops and Robber games,
Linear Programming,
Tree,
Grid.
[bibtex-entry]
-
Nathann Cohen and David Coudert.
Le défi des 1001 graphes.
Interstices,
December 2017.
[WWW
]
Keywords:
théorie des graphes,
cycle hamiltonien,
algorithmes.
[bibtex-entry]
-
Nathann Cohen,
David Coudert,
Guillaume Ducoffe,
and Aurélien Lancin.
Applying clique-decomposition for computing Gromov hyperbolicity.
Theoretical Computer Science,
690:114-139,
2017.
[WWW
] [PDF
]
Keywords:
clique-decomposition,
graph algorithms,
outerplanar graphs,
Gromov hyperbolicity.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Raul Lopes.
Bispindle in strongly connected digraphs with large chromatic number.
Electronic Notes in Discrete Mathematics,
62:69 - 74,
November 2017.
[WWW
] [PDF
]
Keywords:
subdivision,
Digraph,
chromatic number.
[bibtex-entry]
-
Joergen Bang-Jensen,
Nathann Cohen,
and Frédéric Havet.
Finding good 2-partitions of digraphs II. Enumerable properties.
Journal of Theoretical Computer Science (TCS),
640:1-19,
August 2016.
[WWW
] [PDF
]
Keywords:
Feedback vertex set,
Out-branching,
Tournament,
Oriented,
NP-complete,
Polynomial,
Partition,
Splitting digraphs,
Acyclic,
Semicomplete digraph,
2-Partition,
Minimum degree.
[bibtex-entry]
-
Julio Araujo,
Nathann Cohen,
Susanna F. De Rezende,
Frédéric Havet,
and Phablo Moura.
On the proper orientation number of bipartite graphs.
Journal of Theoretical Computer Science (TCS),
566:59-75,
February 2015.
[WWW
] [Abstract] [bibtex-entry]
-
Nathann Cohen,
David Coudert,
and Aurélien Lancin.
On computing the Gromov hyperbolicity.
ACM Journal on Experimental Algorithmics,
20(1):18,
2015.
[WWW
] [PDF
]
Keywords:
Algorithms,
Gromov Hyperbolicity,
Networks.
[Abstract] [bibtex-entry]
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
Discrete Applied Mathematics,
160(18):2501-2513,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
V. Andova,
N. Cohen,
and R. Skrekovski.
Graph Classes (Dis)satisfying the Zagreb Indices Inequality.
MATCH Commun. Math. Comput. Chem.,
65(3):647-658,
2011.
[PDF
] [Abstract] [bibtex-entry]
-
M. Basavaraju,
L. S. Chandran,
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edge-coloring of planar graphs.
SIAM Journal of Discrete Mathematics,
25(2):463--478,
2011.
[PDF
] [Abstract] [bibtex-entry]
-
J-C. Bermond,
Y. M. Chee,
N. Cohen,
and X. Zhang.
The $\alpha$-Arboricity of Complete Uniform Hypergraphs.
SIAM Journal on Discrete Mathematics,
25(2):600-610,
2011.
[PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
Theoretical Computer Science (TCS),
412(35):4675-4687,
August 2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen and F. Havet.
Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree.
Graphs and Combinatorics,
27(6):831-849,
2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
A. Casamayou,
N. Cohen,
G. Connan,
T. Dumont,
L. Fousse,
F. Maltey,
M. Meulien,
M. Mezzarobba,
C. Pernet,
N.M. Thiéry,
and P. Zimmermann.
Calcul mathématique avec Sage,
chapter Théorie des graphes.
2010.
[WWW
] [bibtex-entry]
-
A. Casamayou,
N. Cohen,
G. Connan,
T. Dumont,
L. Fousse,
F. Maltey,
M. Meulien,
M. Mezzarobba,
C. Pernet,
N. M. Thiéry,
and P. Zimmermann.
Calcul mathématique avec Sage,
chapter Programmation Linéaire.
2010.
[WWW
] [bibtex-entry]
-
N. Cohen,
D. Dimitrov,
R. Krakovski,
R. Skrekovski,
and V. Vukasinovic.
On Wiener Index of Graphs and Their Line Graphs.
MATCH Commun. Math. Comput. Chem.,
64(3):683-698,
2010.
[PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
F. V. Fomin,
G. Gutin,
E. Jung Kim,
S. Saurabh,
and A. Yeo.
Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.
Journal of Computer and System Sciences,
76(7):650 - 662,
2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen and F. Havet.
Planar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof.
Discrete Mathematics,
310(21):3049--3051,
2010.
[PDF
]
Keywords:
edge-colouring,
list colouring,
List Colouring Conjecture,
planar graphs.
[Abstract] [bibtex-entry]
-
Thibaud Trolliet,
Nathann Cohen,
Frédéric Giroire,
Luc Hogie,
and Stéphane Pérennes.
Coefficient de Clustering d'intérêt : une nouvelle métrique pour les graphes dirigés comme Twitter.
In ALGOTEL 2020 -- 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Lyon, France,
September 2020.
[WWW
] [PDF
]
Keywords:
Systèmes Complexes,
Coefficient de Clustering,
Graphes Dirigés,
Réseaux Sociaux,
Twitter.
[bibtex-entry]
-
Thibaud Trolliet,
Nathann Cohen,
Frédéric Giroire,
Luc Hogie,
and Stéphane Pérennes.
Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter.
In COMPLEX NETWORKS 2020 - The 9th International Conference on Complex Networks and their Applications,
Madrid / Virtual, Spain,
December 2020.
[WWW
] [PDF
]
Keywords:
Complex networks,
Clustering Coefficient,
Directed networks,
Social networks,
Twitter.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
Dorian Mazauric,
Ignasi Sau,
and Rémi Watrigant.
Complexity Dichotomies for the Minimum $F$-Overlay Problem.
In IWOCA: International Workshop on Combinatorial Algorithms,
Newcastle, Australia,
pages 12,
July 2017.
[WWW
] [PDF
]
Keywords:
Fixed-parameter tractability,
Hypergraph,
Minimum F-Overlay Problem,
NP-completeness.
[bibtex-entry]
-
Nathann Cohen,
Nìcolas A Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Enquêter dans les graphes.
In ALGOTEL 2017 - 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Quiberon, France,
May 2017.
[WWW
] [PDF
]
Keywords:
Jeu de Gendarmes et Voleur,
Programmation Linéaire,
Mots-clefs : Jeux combinatoires à deux joueurs dans les graphes.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a combinatorial game in graphs through Linear Programming.
In 28th International Symposium on Algorithms and Computation (ISAAC 2017),
Phuket, Thailand,
2017.
[WWW
] [PDF
]
Keywords:
Turn-by-turn games in graphs,
Graph algorithms,
Linear Programming.
[bibtex-entry]
-
Jean-Claude Bermond,
Nathann Cohen,
David Coudert,
Dimitrios Letsios,
Ioannis Milis,
Stéphane Pérennes,
and Vassilis Zissimopoulos.
Bin Packing with Colocations.
In Klaus Jansen and Monaldo Mastrolilli, editors,
14th International Workshop on Approximation and Online Algorithms (WAOA),
volume 10138,
Aarhus, Denmark,
pages 40-51,
August 2016.
Springer.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
In Bordeaux Graph Wokshop 2016,
Bordeaux, France,
pages 85-88,
November 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
In Erik D. Demaine and Fabrizio Grandoni, editors,
8th International Conference on Fun with Algorithms, FUN 2016,
volume 49 of Leibniz International Proceedings in Informatics (LIPIcs),
La Maddalena, Maddalena Islands, Italy,
2016.
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Nathann Cohen,
Susanna de Rezende,
Frédéric Havet,
and Phablo Moura.
On the proper orientation number of bipartite graphs.
In 9th International colloquium on graph theory and combinatorics,
Grenoble, France,
June 2014.
[WWW
] [PDF
]
Keywords:
proper orientation,
graph colouring,
bipartite graph,
hardness.
[bibtex-entry]
-
N. Cohen,
D. Coudert,
and A. Lancin.
Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe.
In N. Nisse,
Franck Rousseau,
and Yann Busnel, editors,
15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel),
Pornic, France,
pages 1-4,
May 2013.
Note: Page 1-4.
[WWW
] [PDF
] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in routing reconfiguration problems.
In Maria Gradinariu Potop-Butucaru et Hervé Rivano, editor,
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Belle Dune France,
pages 4p,
2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
In P. Boldi and L. Gargano, editors,
Fifth International conference on Fun with Algorithms (FUN 2010),
volume 6099 of Lecture Notes in Computer Science,
Ischia Island, Italy,
pages 121-132,
June 2010.
Springer.
Note: Http://hal.inria.fr/inria-00495443.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
In proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'09),
volume 35 of Electronic Notes in Discrete Mathematics,
Gramado, Brazil,
pages 275--280,
December 2009.
Springer.
[PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
F. V. Fomin,
G. Gutin,
E. J. Kim,
S. Saurabh,
and A. Yeo.
Algorithm for Finding it -Vertex Out-trees and Its Application to it -Internal Out-branching Problem.
In 15th Annual International Conference on Computing and Combinatorics (COCOON),
volume 5609 of Lecture Notes in Computer Science,
pages 37-46,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edge-colouring of planar graphs.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009),
volume 34 of Electronic Notes on Discrete Mathematics,
Bordeaux, France,
pages 417-421,
September 2009.
[PDF
] [Abstract] [bibtex-entry]
-
Nathann Cohen,
Nìcolas A Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Spy-Game on graphs: complexity and simple topologies.
Research Report,
Inria Sophia Antipolis,
2017.
[WWW
] [PDF
]
Keywords:
PSPACE-hard,
Cops and Robber games,
graphs.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a combinatorial game in graphs through Linear Programming.
Research Report,
Inria Sophia Antipolis,
2017.
[WWW
] [PDF
]
Keywords:
Linear Programming,
Cops and Robber games,
Graphs.
[bibtex-entry]
-
Jorgen Bang-Jensen,
Nathann Cohen,
and Frédéric Havet.
Finding good 2-partitions of digraphs II. Enumerable properties.
Research Report RR-8868,
INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Jean-Claude Bermond,
Nathann Cohen,
David Coudert,
Dimitrios Letsios,
Ioannis Milis,
Stéphane Pérennes,
and Vassilis Zissimopoulos.
Bin packing with colocations.
Research Report,
Inria ; I3S,
October 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
Research Report RR-8865,
LRI - CNRS, University Paris-Sud ; LIP - ENS Lyon ; INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
Research Report RR-8869,
Inria,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Nathann Cohen,
Susanna F. De Rezende,
Frédéric Havet,
and Phablo Moura.
On the proper orientation number of bipartite graphs.
Research Report RR-8492,
INRIA,
March 2014.
[WWW
] [PDF
]
Keywords:
proper orientation,
graph colouring,
bipartite graph.
[bibtex-entry]
-
Nathann Cohen,
David Coudert,
Guillaume Ducoffe,
and Aurélien Lancin.
Applying clique-decomposition for computing Gromov hyperbolicity.
Research Report RR-8535,
INRIA,
June 2014.
[WWW
] [PDF
]
Keywords:
Hyperbolicity,
Algorithms,
Graphs,
Decomposition.
[bibtex-entry]
-
N. Cohen,
D. Coudert,
and A. Lancin.
Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs.
Technical report RR-8074,
INRIA,
September 2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen and F. Havet.
Linear and 2-frugal choosability of graphs of small maximum average degree.
Research Report RR-7213,
INRIA,
02 2010.
[WWW
] [Abstract] [bibtex-entry]
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
Research Report 6934,
INRIA,
2009.
[WWW
] [PDF
]
Keywords:
graph theory,
complexity,
edge-labelling,
planar graphs,
matching-cut,
channel assignment.
[Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks..
Technical report RR-7047,
INRIA,
September 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edge-colouring of planar graphs.
Research Report 6876,
INRIA,
March 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen and F. Havet.
Planar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof.
Research Report RR-7098,
November 2009.
[WWW
]
Keywords:
edge-colouring,
list colouring,
List Colouring Conjecture,
planar graphs.
[Abstract] [bibtex-entry]
-
Nathann Cohen.
Several Graph problems and their Linear Program formulations.
Note: Working paper or preprint,
January 2019.
[WWW
] [PDF
] [bibtex-entry]
-
N. Cohen.
Several Graph Problems and their LP formulation,
2010.
[PDF
] [Abstract] [bibtex-entry]
-
N. Cohen.
Coloration des graphes planaires,
July 2008.
Note: Internship report.
[PDF
] [bibtex-entry]
BACK TO COATI PUBLICATION INDEX
Last modified: Sat Jan 29 19:00:43 2022
