Publications of Nathann Cohen

BACK TO COATI PUBLICATION INDEX

Publications of Nathann Cohen

Thesis
  1. 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]
     
Articles in journal or book's chapters
  1. Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. Theoretical Computer Science, 2017. [WWW ] [PDF ]
    Keywords: outerplanar graphs, Gromov hyperbolicity, graph algorithms, clique-decomposition. [bibtex-entry]
     
  2. 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]
     
  3. 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]
     
  4. 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]
     
  5. 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]
     
  6. 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]
     
  7. 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]
     
  8. 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]
     
  9. 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]
     
  10. 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]
     
  11. 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]
     
  12. 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]
     
  13. 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]
     
  14. 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]
     
  15. 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]
     
Conference's articles
  1. Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, and Rémi Watrigant. Complexity Dichotomies for the Minimum F -Overlay Problem. In IWOCA 2017 - 28th International Workshop on Combinatorial Algorithms, Newcastle, Australia, pages 12, July 2017. [WWW ] [PDF ]
    Keywords: Hypergraph, Minimum F-Overlay Problem, NP-completeness, Fixed-parameter tractability. [bibtex-entry]
     
  2. Nathann Cohen, Nìcolas 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: Programmation Linéaire, Mots-clefs : Jeux combinatoires à deux joueurs dans les graphes, Jeu de Gendarmes et Voleur. [bibtex-entry]
     
  3. 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]
     
  4. 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]
     
  5. 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]
     
  6. 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]
     
  7. 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]
     
  8. 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]
     
  9. 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]
     
  10. 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]
     
  11. 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]
     
  12. 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]
     
  13. 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]
     
Internal reports
  1. Nathann Cohen, Nìcolas 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: Cops and Robber games, graphs, PSPACE-hard. [bibtex-entry]
     
  2. 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]
     
  3. 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]
     
  4. 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]
     
  5. 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]
     
  6. 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]
     
  7. 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]
     
  8. 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]
     
  9. 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]
     
  10. 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]
     
  11. 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]
     
  12. 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]
     
  13. 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]
     
  14. 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]
     
Miscellaneous
  1. N. Cohen. Several Graph Problems and their LP formulation, 2010. [PDF ] [Abstract] [bibtex-entry]
     
  2. N. Cohen. Coloration des graphes planaires, July 2008.
    Note: Internship report. [PDF ] [bibtex-entry]
     

BACK TO COATI PUBLICATION INDEX



Last modified: Fri Oct 20 15:06:06 2017