Skip to Main content
Number of documents

61

Publications


Journal articles30 documents

Conference papers30 documents

  • Pierre Bergé, Guillaume Ducoffe, Michel Habib. Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Mar 2022, Marseille, France. ⟨10.4230/LIPIcs.STACS.2022.9⟩. ⟨hal-03603802⟩
  • Guillaume Ducoffe. On computing the average distance for some chordal-like graphs. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.44⟩. ⟨hal-03323471⟩
  • Guillaume Ducoffe. Beyond Helly graphs: the diameter problem on absolute retracts. 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), Jun 2021, Warsaw (online), Poland. pp.321-335, ⟨10.1007/978-3-030-86838-3_25⟩. ⟨hal-03350582⟩
  • Feodor F Dragan, Guillaume Ducoffe, Heather M Guarnera. Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs. Algorithms and Data Structures 17th International Symposium (WADS 2021), Aug 2021, Halifax, Nova Scotia (Virtual Event), Canada. pp.300-314, ⟨10.1007/978-3-030-83508-8_22⟩. ⟨hal-03315928⟩
  • Guillaume Ducoffe. Maximum Matching in almost linear time on graphs of bounded clique-width. 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021, Lisbon (virtual event), Portugal. ⟨10.4230/LIPIcs.IPEC.2021.15⟩. ⟨hal-03445479⟩
  • Guillaume Ducoffe. Optimal centrality computations within bounded clique-width graphs. 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021, Lisbon (virtual event), Portugal. ⟨10.4230/LIPIcs.IPEC.2021.16⟩. ⟨hal-03445484⟩
  • Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle. Treelength of Series-parallel graphs. LAGOS 2021 - XI Latin and American Algorithms, Graphs and Optimization Symposium, May 2021, São Paulo / Virtual, Brazil. ⟨10.1016/j.procs.2021.11.008⟩. ⟨hal-03175837⟩
  • Guillaume Ducoffe. Isometric embeddings in trees and their use in distance problems. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.43⟩. ⟨hal-03323472⟩
  • 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-03373614⟩
  • 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. 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⟩
  • 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, Ruxandra Marinescu-Ghemeci, Camelia Obreja, Alexandru Popa, Rozica Maria 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 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⟩
  • 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⟩
  • 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⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor F. 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⟩
  • Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Camelia Obreja, Alexandru Popa, Rozica Maria 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, 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. 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⟩
  • 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. 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. 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, 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, 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⟩