Publications of Guillaume Ducoffe

BACK TO COATI PUBLICATION INDEX

Publications of Guillaume Ducoffe

Thesis
  1. Guillaume Ducoffe. Metric properties of large graphs. Theses, Université Côte d'Azur, December 2016. [WWW ] [PDF ]
    Keywords: Graph, Algorithms, Complexity in P, Gromov Hyperbolicity, Treelength, Treebreadth, Treewidth, Coloring games, Nash equilibrium, Boolean function learning, Algorithmes, Complexité dans P, Hyperbolicité, Jeux de coloration, Équilibre de Nash, Apprentissage de fonction booléenne, Graphe. [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. David Coudert, Guillaume Ducoffe, and Nicolas Nisse. To Approximate Treewidth, Use Treelength!. Siam Journal on Discrete Mathematics, 30(3):13, 2016. [WWW ] [PDF ]
    Keywords: Graph, Treewidth, Treelength, Cycle basis, Genus. [bibtex-entry]
     
  3. David Coudert and Guillaume Ducoffe. Data center interconnection networks are not hyperbolic. Theoretical Computer Science, 639:72-90, 2016. [WWW ] [PDF ]
    Keywords: interconnection network, data center, Cayley graph, greedy routing scheme, metric embedding, graph endomorphism, Gromov hy-perbolicity. [bibtex-entry]
     
  4. David Coudert and Guillaume Ducoffe. On the hyperbolicity of bipartite graphs and intersection graphs. Discrete Applied Mathematics, 214:187-195, 2016. [WWW ] [PDF ]
    Keywords: biclique graph, line graph, clique graph, Gromov hyperbolicity, bipartite graph, intersection graph, graph power. [bibtex-entry]
     
  5. Julio Araujo, Jean-Claude Bermond, and Guillaume Ducoffe. Eulerian and Hamiltonian dicycles in directed hypergraphs. Discrete Mathematics, Algorithms and Applications, 06:1450012, 2014. [WWW ] [PDF ]
    Keywords: Eulerian and Hamiltonian dicycles, 11xxx, de Bruijn dihyper-graphs Mathematics Subject Classification 2000: 11xxx, Directed hypergraphs. [bibtex-entry]
     
  6. David Coudert and Guillaume Ducoffe. Recognition of C4-free and 1/2-hyperbolic graphs. Siam Journal on Discrete Mathematics, 28(3):1601-1617, September 2014. [WWW ] [PDF ]
    Keywords: rectangular matrix multiplication, Hyperbolicity, discrete metric space, graph algorithms, C4-free graphs, rectangular matrix multiplication.. [bibtex-entry]
     
Conference's articles
  1. David Coudert and Guillaume Ducoffe. A simple approach for lower-bounding the distortion in any Hyperbolic embedding. In EUROCOMB'17 -- The European Conference on Combinatorics, Graph Theory and Applications, volume 61, Vienna, Austria, pages 293 - 299, August 2017. Elsevier. [WWW ] [PDF ]
    Keywords: Gromov hyperbolicity, Hyperbolic space, Cop and Robber games. [bibtex-entry]
     
  2. David Coudert and Guillaume Ducoffe. Liens entre symétries et étirements de routages dans les réseaux d'interconnexions de centres de données. In ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Bayonne, France, May 2016. [WWW ] [PDF ]
    Keywords: Mots-clefs : Graphe, Centre de données, Routage géométrique, Endomorphisme de graphe, Hyperbolicité. [bibtex-entry]
     
  3. Guillaume Ducoffe, Sylvain Legay, and Nicolas Nisse. On the Complexity of Computing Treebreadth. In Veli Mäkinen, Simon J. Puglisi, and Leena Salmela, editors, 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, number 9843 of Combinatorial Algorithms, Helsinki, Finland, pages 3-15, August 2016. Springer International Publishing. [WWW ] [PDF ] [bibtex-entry]
     
  4. Guillaume Ducoffe. The Parallel Complexity of Coloring Games. In Martin Gairing and Rahul Savani, editors, 9th International Symposium, SAGT 2016, number 9928 of Algorithmic Game Theory, Liverpool, United Kingdom, pages 27-39, September 2016. Springer International Publishing. [WWW ] [PDF ] [bibtex-entry]
     
  5. Augustin Chaintreau, Guillaume Ducoffe, Roxana Geambasu, and Mathias Lécuyer. Vers une plus grande transparence du Web. In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France, June 2015. [WWW ] [PDF ]
    Keywords: Algorithmes d'apprentissage, Formes normales disjonctives monotones, Annonces publicitaires ciblées, Sécurité de l'information (Privacy). [Abstract] [bibtex-entry]
     
  6. David Coudert, Guillaume Ducoffe, and Nicolas Nisse. Structure vs métrique dans les graphes. In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France, June 2015. [WWW ] [PDF ]
    Keywords: Genre, Hyperbolicité, Graphe, Largeur arborescente (Treewidth), Longueur arborescente (Treelength). [Abstract] [bibtex-entry]
     
  7. Mathias Lecuyer, Guillaume Ducoffe, Francis Lan, Andrei Papancea, Theofilos Petsios, Riley Spahn, Augustin Chaintreau, and Roxana Geambasu. XRay: Enhancing the Web's Transparency with Differential Correlation. In USENIX Security Symposium, San Diego, United States, August 2014.
    Note: Extended version of a paper presented at the 23rd USENIX Security Symposium (USENIX Security 14). [WWW ] [PDF ] [bibtex-entry]
     
Internal reports
  1. David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. Research Report, Inria - Sophia antipolis ; Universite Cote d'Azur ; University of Bucharest, Faculty of Mathematics and Computer Science ; National Institute for Research and Development in Informatics, Romania, July 2017. [WWW ] [PDF ]
    Keywords: Neighbourhood diversity, Primeval decomposition, Clique-width, Modular decomposition, Split decomposition, Hardness in P, Fully polynomial FPT, Graph algorithms. [bibtex-entry]
     
  2. Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, and Alexandru Popa. On the (di)graphs with (directed) proper connection number two. Research Report, Université Côte d’Azur, Inria, CNRS, I3S, France ; University of Bucharest, Faculty of Mathematics and Computer Science ; National Institute for Research and Development in Informatics, Romania ; The Research Institute of the University of Bucharest ICUB, Romania, March 2017. [WWW ] [PDF ] [bibtex-entry]
     
  3. Guillaume Ducoffe. Finding cut-vertices in the square roots of a graph. Research Report, Université Côte d’Azur, Inria, CNRS, I3S, France, February 2017. [WWW ] [PDF ]
    Keywords: square root, biconnected components, clique cutset, cactus-block graph, Gallai tree, cycle-power graph, circular-arc graph. [bibtex-entry]
     
  4. Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, and Karol Suchan. On interval number in cycle convexity. Research Report, Inria Sophia Antipolis ; I3S, 2016. [WWW ] [PDF ]
    Keywords: graph, convexity, complexity, dominating set. [bibtex-entry]
     
  5. David Coudert and Guillaume Ducoffe. Clique-decomposition revisited. Research Report, INRIA Sophia Antipolis - I3S, February 2016. [WWW ] [PDF ]
    Keywords: planar graphs, treewidth, clique-decomposition, minimal triangulation, clique-number, bounded-degree graphs. [bibtex-entry]
     
  6. David Coudert, Guillaume Ducoffe, Nicolas Nisse, and Mauricio Soto. Distance-preserving orderings in graphs. Research Report RR-8973, Inria Sophia Antipolis, 2016. [WWW ] [PDF ]
    Keywords: bounded treewidth, distance-preserving elimination ordering, metric graph theory, NP-complete, exact expo- nential algorithm, integer linear programming. [bibtex-entry]
     
  7. Guillaume Ducoffe, Sylvain Legay, and Nicolas Nisse. On computing tree and path decompositions with metric constraints on the bags. Research Report RR-8842, INRIA Sophia Antipolis - Méditerranée ; LRI - CNRS, University Paris-Sud, January 2016. [WWW ] [PDF ]
    Keywords: path-breadth, k-good tree decompositions, tree-length, tree-breadth, path-length. [bibtex-entry]
     
  8. David Coudert and Guillaume Ducoffe. Data center interconnection networks are not hyperbolic. Research Report, Inria Sophia Antipolis ; I3S ; Université Nice Sophia Antipolis ; CNRS, May 2015. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  9. 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]
     
  10. David Coudert, Guillaume Ducoffe, and Nicolas Nisse. Diameter of Minimal Separators in Graphs. Research Report RR-8639, Inria Sophia Antipolis ; I3S ; INRIA, November 2014. [WWW ] [PDF ] [bibtex-entry]
     
  11. David Coudert and Guillaume Ducoffe. On the recognition of $C\_4$-free and $1/2$-hyperbolic graphs. Research Report RR-8458, INRIA, January 2014. [WWW ] [PDF ] [bibtex-entry]
     
  12. G. Ducoffe. Eulerian and Hamiltonian Directed Hypergraphs. Technical report RR-7893, INRIA, 2012. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
Miscellaneous
  1. Guillaume Ducoffe, Mathias Lécuyer, Augustin Chaintreau, and Roxana Geambasu. Web Transparency for Complex Targeting: Algorithms, Limits, and Tradeoffs. SIGMETRICS '15 Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, June 2015.
    Note: Poster. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     

BACK TO COATI PUBLICATION INDEX



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