Skip to Main content
Number of documents

43

Publications


Journal articles20 documents

  • Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. Algorithmica, Springer Verlag, In press, ⟨10.1007/s00453-019-00657-7⟩. ⟨hal-02528905⟩
  • David Coudert, Guillaume Ducoffe, Alexandru Popa. P-FPT algorithms for bounded clique-width graphs. ACM Transactions on Algorithms, Association for Computing Machinery, 2019, 15 (3), pp.1-57. ⟨10.1145/3310228⟩. ⟨hal-02152971⟩
  • Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. Discrete Applied Mathematics, Elsevier, 2019, 270, pp.37-57. ⟨10.1016/j.dam.2019.07.023⟩. ⟨hal-02264327⟩
  • Guillaume Ducoffe. Finding cut-vertices in the square roots of a graph. Discrete Applied Mathematics, Elsevier, 2019, 257, pp.158-174. ⟨hal-01948839⟩
  • Guillaume Ducoffe, Arne Leitert. Equivalence between pathbreadth and strong pathbreadth. Discrete Applied Mathematics, Elsevier, 2019, 262, pp.185-188. ⟨10.1016/j.dam.2019.02.009⟩. ⟨hal-02055113⟩
  • Daniela Aguirre-Guerrero, Guillaume Ducoffe, Lluis Fabrega, Pere Vila, David Coudert. Low Time Complexity Algorithms for Path Computation in Cayley Graphs. Discrete Applied Mathematics, Elsevier, 2019, 259, pp.218-225. ⟨10.1016/j.dam.2018.12.005⟩. ⟨hal-01973608⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discrete and Computational Geometry, Springer Verlag, In press, ⟨10.1007/s00454-019-00107-9⟩. ⟨hal-02149991⟩
  • Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa. On the (di)graphs with (directed) proper connection number two. Discrete Applied Mathematics, Elsevier, 2019, ⟨10.1016/j.dam.2019.06.024⟩. ⟨hal-02179551⟩
  • Guillaume Ducoffe. Easy computation of eccentricity approximating trees. Discrete Applied Mathematics, Elsevier, 2019, 260, pp.267-271. ⟨hal-02011252⟩
  • David Coudert, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto. On distance-preserving elimination orderings in graphs: Complexity and algorithms. Discrete Applied Mathematics, Elsevier, 2018, 243, pp.140-153. ⟨10.1016/j.dam.2018.02.007⟩. ⟨hal-01741277⟩
  • David Coudert, Guillaume Ducoffe. Revisiting Decomposition by Clique Separators. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.682 - 694. ⟨10.1137/16M1059837⟩. ⟨hal-01753324⟩
  • Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan. On interval number in cycle convexity. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2018, Vol. 20 no. 1 (1), pp.1-28. ⟨hal-01394201v4⟩
  • Guillaume Ducoffe. A short note on the complexity of computing strong pathbreadth. Information Processing Letters, Elsevier, 2018, 133, pp.56-58. ⟨10.1016/j.ipl.2018.01.005⟩. ⟨hal-01735826⟩
  • Nathann Cohen, David Coudert, Guillaume Ducoffe, Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114-139. ⟨10.1016/j.tcs.2017.06.001⟩. ⟨hal-01540756⟩
  • David Coudert, Guillaume Ducoffe. On the hyperbolicity of bipartite graphs and intersection graphs. Discrete Applied Mathematics, Elsevier, 2016, 214, pp.187-195. ⟨10.1016/j.dam.2016.06.017⟩. ⟨hal-01220132v2⟩
  • David Coudert, Guillaume Ducoffe. Data center interconnection networks are not hyperbolic. Theoretical Computer Science, Elsevier, 2016, 639, pp.72-90. ⟨10.1016/j.tcs.2016.05.025⟩. ⟨hal-01323301⟩
  • David Coudert, Guillaume Ducoffe, Nicolas Nisse. To Approximate Treewidth, Use Treelength!. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.13. ⟨10.1137/15M1034039⟩. ⟨hal-01348965⟩
  • Julio Araujo, Jean-Claude Bermond, Guillaume Ducoffe. Eulerian and Hamiltonian dicycles in directed hypergraphs. Discrete Mathematics, Algorithms and Applications, World Scientific Publishing, 2014, 06, pp.1450012. ⟨10.1142/S1793830914500128⟩. ⟨hal-01104634v2⟩
  • David Coudert, Guillaume Ducoffe. Recognition of C4-free and 1/2-hyperbolic graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (3), pp.1601-1617. ⟨10.1137/140954787⟩. ⟨hal-01070768⟩
  • Guillaume Ducoffe. Hamiltonicity of large generalized de Bruijn cycles. Discrete Applied Mathematics, Elsevier, 2013, 161, pp.2200 - 2204. ⟨10.1016/j.dam.2013.02.027⟩. ⟨hal-01103786⟩

Conference papers22 documents

  • Guillaume Ducoffe, Michel Habib, Laurent Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. SODA 2020 - ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. ⟨hal-02340382⟩
  • Guillaume Ducoffe, Michel Habib, Laurent Viennot. Fast Diameter Computation within Split Graphs. COCOA 2019 - 13th Annual International Conference on Combinatorial Optimization and Applications, Dec 2019, Xiamen, China. ⟨hal-02307397v2⟩
  • Guillaume Ducoffe. A new application of Orthogonal Range Searching for computing Giant Graph Diameters. 2nd Symposium on Simplicity in Algorithms (SOSA 2019), Jan 2019, San Diego, CA, United States. pp.12:1-12:7, ⟨10.4230/OASIcs.SOSA.2019.12⟩. ⟨hal-01974190⟩
  • Guillaume Ducoffe. The 4-Steiner Root Problem. 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019), Jun 2019, Vall de Nuria, Spain. pp.14-26, ⟨10.1007/978-3-030-30786-8_2⟩. ⟨hal-02290671⟩
  • Guillaume Ducoffe. Faster approximation algorithms for computing shortest cycles on weighted graphs. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Jul 2019, Patras, Greece. ⟨10.4230/LIPIcs.ICALP.2019.44⟩. ⟨hal-02173350⟩
  • Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. FUN 2018 - 9th International Conference on Fun with Algorithms, 2018, La Maddalena, Italy. ⟨hal-01780627⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry (SoCG 2018), Jun 2018, Budapest, Hungary. pp.22, ⟨10.4230/LIPIcs.SoCG.2018.22⟩. ⟨hal-01836063⟩
  • David Coudert, Guillaume Ducoffe, Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.20, ⟨10.1137/1.9781611975031.176⟩. ⟨hal-01676187⟩
  • Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Camelia Obreja, Alexandru Popa, Rozica Tache. Extremal Graphs with respect to the Modified First Zagreb Connection Index. 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Sep 2018, Timisoara, Romania. ⟨10.1109/SYNASC.2018.00033⟩. ⟨hal-02011274⟩
  • Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Camelia Obreja, Alexandru Popa, Rozica Tache. Extremal Graphs with respect to the Modified First Zagreb Connection Index. Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW), Jun 2018, Paris, France. ⟨hal-02011265⟩
  • Guillaume Ducoffe, Alexandru Popa. The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. 29th International Symposium on Algorithms and Computation (ISAAC 2018), Dec 2018, Jiaoxi, Yilan County, Taiwan. ⟨10.4230/LIPIcs.ISAAC.2018.144⟩. ⟨hal-01955985⟩
  • Guillaume Ducoffe, Alexandru Popa. The b-Matching problem in distance-hereditary graphs and beyond. 29th International Symposium on Algorithms and Computation (ISAAC 2018), Dec 2018, Jiaoxi, Yilan County, Taiwan. pp.1 - 122, ⟨10.4230/LIPIcs.ISAAC.2018.122⟩. ⟨hal-01955994⟩
  • David Coudert, Guillaume Ducoffe. A simple approach for lower-bounding the distortion in any Hyperbolic embedding. EUROCOMB'17 -- The European Conference on Combinatorics, Graph Theory and Applications, Aug 2017, Vienna, Austria. pp.293 - 299, ⟨10.1016/j.endm.2017.06.051⟩. ⟨hal-01573042⟩
  • Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa. On the (di)graphs with (directed) proper connection number two. IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Sep 2017, Marseille, France. pp.237 - 242, ⟨10.1016/j.endm.2017.10.041⟩. ⟨hal-01625042⟩
  • Guillaume Ducoffe. Finding cut-vertices in the square roots of a graph. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Jun 2017, Eindhoven, Netherlands. pp.234--248, ⟨10.1007/978-3-319-68705-6_18⟩. ⟨hal-01627959⟩
  • Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, Aug 2016, Helsinki, Finland. pp.3-15, ⟨10.1007/978-3-319-44543-4_1⟩. ⟨hal-01354996⟩
  • David Coudert, Guillaume Ducoffe. Liens entre symétries et étirements de routages dans les réseaux d'interconnexions de centres de données. ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2016, Bayonne, France. ⟨hal-01302470⟩
  • Guillaume Ducoffe. The Parallel Complexity of Coloring Games. 9th International Symposium, SAGT 2016, Sep 2016, Liverpool, United Kingdom. pp.27-39, ⟨10.1007/978-3-662-53354-3_3⟩. ⟨hal-01361056⟩
  • David Coudert, Guillaume Ducoffe, Nicolas Nisse. Structure vs métrique dans les graphes. ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France. ⟨hal-01144694⟩
  • Augustin Chaintreau, Guillaume Ducoffe, Roxana Geambasu, Mathias Lécuyer. Vers une plus grande transparence du Web. ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France. ⟨hal-01144787⟩
  • Mathias Lecuyer, Guillaume Ducoffe, Francis Lan, Andrei Papancea, Theofilos Petsios, et al.. XRay: Enhancing the Web's Transparency with Differential Correlation. USENIX Security Symposium, Aug 2014, San Diego, United States. ⟨hal-01100757⟩
  • Guillaume Ducoffe, Dorian Mazauric, Augustin Chaintreau. De la difficulté de garder ses amis (quand on a des ennemis) !. 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2013, Pornic, France. pp.1-4. ⟨hal-00815680⟩

Poster communications1 document

  • Guillaume Ducoffe, Mathias Lécuyer, Augustin Chaintreau, 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, Jun 2015, Portland, Oregon, United States. ⟨10.1145/2745844.2745896⟩. ⟨hal-01163552⟩