![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Guillaume Ducoffe
Person information
- affiliation: University of Bucharest, Romania
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2016
- [b1]Guillaume Ducoffe:
Metric properties of large graphs. (Propriétés métriques des grands graphes). University of Côte d'Azur, France, 2016
Journal Articles
- 2024
- [j38]Feodor F. Dragan, Guillaume Ducoffe:
α i-Metric Graphs: Radius, Diameter and all Eccentricities. Algorithmica 86(7): 2092-2129 (2024) - [j37]Pierre Bergé, Guillaume Ducoffe, Michel Habib:
Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs. Theory Comput. Syst. 68(1): 144-193 (2024) - [j36]Guillaume Ducoffe
:
Balancing graph Voronoi diagrams with one more vertex. Networks 83(2): 368-389 (2024) - 2023
- [j35]Thomas Dissaux
, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle:
Treelength of series-parallel graphs. Discret. Appl. Math. 341: 16-30 (2023) - [j34]Guillaume Ducoffe:
Distance problems within Helly graphs and k-Helly graphs. Theor. Comput. Sci. 946: 113690 (2023) - 2022
- [j33]Guillaume Ducoffe:
Optimal Centrality Computations Within Bounded Clique-Width Graphs. Algorithmica 84(11): 3192-3222 (2022) - [j32]Guillaume Ducoffe:
Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width. Algorithmica 84(11): 3489-3520 (2022) - [j31]Guillaume Ducoffe
:
The diameter of AT-free graphs. J. Graph Theory 99(4): 594-614 (2022) - [j30]Augustin Chaintreau
, Guillaume Ducoffe, Dorian Mazauric:
Non-Existence of Stable Social Groups in Information-Driven Networks. Theory Comput. Syst. 66(4): 758-777 (2022) - [j29]Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension. SIAM J. Comput. 51(5): 1506-1534 (2022) - [j28]Guillaume Ducoffe:
Eccentricity queries and beyond using hub labels. Theor. Comput. Sci. 930: 128-141 (2022) - 2021
- [j27]Guillaume Ducoffe, Alexandru Popa
:
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. Discret. Appl. Math. 291: 201-222 (2021) - [j26]Guillaume Ducoffe, Alexandru Popa
:
The b-Matching problem in distance-hereditary graphs and beyond. Discret. Appl. Math. 305: 233-246 (2021) - [j25]Jérémie Chalopin, Victor Chepoi
, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, Yann Vaxès:
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discret. Comput. Geom. 65(3): 856-892 (2021) - [j24]Guillaume Ducoffe, Michel Habib
, Laurent Viennot:
Fast Diameter Computation within Split Graphs. Discret. Math. Theor. Comput. Sci. 23(3) (2021) - [j23]Guillaume Ducoffe
, Feodor F. Dragan:
A story of diameter, radius, and (almost) Helly property. Networks 77(3): 435-453 (2021) - [j22]Guillaume Ducoffe:
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. SIAM J. Discret. Math. 35(2): 953-969 (2021) - 2020
- [j21]Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse:
On the Complexity of Computing Treebreadth. Algorithmica 82(6): 1574-1600 (2020) - [j20]Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa
:
On the (di)graphs with (directed) proper connection number two. Discret. Appl. Math. 281: 203-215 (2020) - 2019
- [j19]Guillaume Ducoffe:
Finding cut-vertices in the square roots of a graph. Discret. Appl. Math. 257: 158-174 (2019) - [j18]Daniela Aguirre-Guerrero
, Guillaume Ducoffe, Lluís Fàbrega
, Pere Vilà, David Coudert
:
Low time complexity algorithms for path computation in Cayley Graphs. Discret. Appl. Math. 259: 218-225 (2019) - [j17]Guillaume Ducoffe:
Easy computation of eccentricity approximating trees. Discret. Appl. Math. 260: 267-271 (2019) - [j16]Guillaume Ducoffe, Arne Leitert:
Equivalence between pathbreadth and strong pathbreadth. Discret. Appl. Math. 262: 185-188 (2019) - [j15]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? Discret. Appl. Math. 270: 37-57 (2019) - [j14]David Coudert
, Guillaume Ducoffe, Alexandru Popa
:
Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs. ACM Trans. Algorithms 15(3): 33:1-33:57 (2019) - 2018
- [j13]David Coudert
, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto:
On distance-preserving elimination orderings in graphs: Complexity and algorithms. Discret. Appl. Math. 243: 140-153 (2018) - [j12]Júlio Araújo
, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan
:
On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci. 20(1) (2018) - [j11]Guillaume Ducoffe:
A short note on the complexity of computing strong pathbreadth. Inf. Process. Lett. 133: 56-58 (2018) - [j10]David Coudert, Guillaume Ducoffe:
Revisiting Decomposition by Clique Separators. SIAM J. Discret. Math. 32(1): 682-694 (2018) - 2017
- [j9]David Coudert, Guillaume Ducoffe:
A simple approach for lower-bounding the distortion in any Hyperbolic embedding. Electron. Notes Discret. Math. 61: 293-299 (2017) - [j8]Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa
:
On the (di)graphs with (directed) proper connection number two. Electron. Notes Discret. Math. 62: 237-242 (2017) - [j7]Nathann Cohen, David Coudert, Guillaume Ducoffe, Aurélien Lancin:
Applying clique-decomposition for computing Gromov hyperbolicity. Theor. Comput. Sci. 690: 114-139 (2017) - 2016
- [j6]David Coudert
, Guillaume Ducoffe:
On the hyperbolicity of bipartite graphs and intersection graphs. Discret. Appl. Math. 214: 187-195 (2016) - [j5]David Coudert, Guillaume Ducoffe, Nicolas Nisse:
To Approximate Treewidth, Use Treelength! SIAM J. Discret. Math. 30(3): 1424-1436 (2016) - [j4]David Coudert
, Guillaume Ducoffe:
Data center interconnection networks are not hyperbolic. Theor. Comput. Sci. 639: 72-90 (2016) - 2014
- [j3]Júlio Araújo
, Jean-Claude Bermond, Guillaume Ducoffe:
Eulerian and Hamiltonian dicycles in Directed hypergraphs. Discret. Math. Algorithms Appl. 6(1) (2014) - [j2]David Coudert, Guillaume Ducoffe:
Recognition of C4-Free and 1/2-Hyperbolic Graphs. SIAM J. Discret. Math. 28(3): 1601-1617 (2014) - 2013
- [j1]Guillaume Ducoffe:
Hamiltonicity of large generalized de Bruijn cycles. Discret. Appl. Math. 161(13-14): 2200-2204 (2013)
Conference and Workshop Papers
- 2024
- [c28]David Coudert, Mónika Csikós, Guillaume Ducoffe, Laurent Viennot:
Practical Computation of Graph VC-Dimension. SEA 2024: 8:1-8:20 - 2023
- [c27]Feodor F. Dragan, Guillaume Ducoffe:
α i-Metric Graphs: Radius, Diameter and all Eccentricities. WG 2023: 276-290 - 2022
- [c26]Guillaume Ducoffe:
Obstructions to Faster Diameter Computation: Asteroidal Sets. IPEC 2022: 10:1-10:24 - [c25]Pierre Bergé, Guillaume Ducoffe, Michel Habib:
Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. STACS 2022: 9:1-9:21 - 2021
- [c24]Guillaume Ducoffe:
Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width. IPEC 2021: 15:1-15:17 - [c23]Guillaume Ducoffe:
Optimal Centrality Computations Within Bounded Clique-Width Graphs. IPEC 2021: 16:1-16:16 - [c22]Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle:
Treelength of Series-parallel Graphs. LAGOS 2021: 30-38 - [c21]Guillaume Ducoffe:
Isometric Embeddings in Trees and Their Use in Distance Problems. MFCS 2021: 43:1-43:16 - [c20]Guillaume Ducoffe:
On Computing the Average Distance for Some Chordal-Like Graphs. MFCS 2021: 44:1-44:16 - [c19]Feodor F. Dragan, Guillaume Ducoffe, Heather M. Guarnera
:
Fast Deterministic Algorithms for Computing All Eccentricities in (Hyperbolic) Helly Graphs. WADS 2021: 300-314 - [c18]Guillaume Ducoffe
:
Beyond Helly Graphs: The Diameter Problem on Absolute Retracts. WG 2021: 321-335 - 2020
- [c17]Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. SODA 2020: 1905-1922 - 2019
- [c16]Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Fast Diameter Computation Within Split Graphs. COCOA 2019: 155-167 - [c15]Guillaume Ducoffe:
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. ICALP 2019: 49:1-49:13 - [c14]Guillaume Ducoffe:
A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. SOSA 2019: 12:1-12:7 - [c13]Guillaume Ducoffe:
The 4-Steiner Root Problem. WG 2019: 14-26 - 2018
- [c12]Jérémie Chalopin, Victor Chepoi
, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, Yann Vaxès:
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. SoCG 2018: 22:1-22:15 - [c11]Florian Kräutli, Matteo Valleriani, Esther Chen, Christoph Sander, Dirk Wintergrün, Sabine Bertram, Gesa Funke, Chantal Wahbi, Manon Gumpert, Victoria Beyer, Nana Citron, Guillaume Ducoffe:
Digital Modelling of Knowledge Innovations In Sacrobosco's Sphere: A Practical Application Of CIDOC-CRM And Linked Open Data With CorpusTracer. DH 2018: 222-224 - [c10]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: 6:1-6:21 - [c9]Guillaume Ducoffe, Alexandru Popa
:
The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes. ISAAC 2018: 6:1-6:13 - [c8]Guillaume Ducoffe, Alexandru Popa
:
The b-Matching Problem in Distance-Hereditary Graphs and Beyond. ISAAC 2018: 30:1-30:13 - [c7]David Coudert, Guillaume Ducoffe, Alexandru Popa
:
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. SODA 2018: 2765-2784 - [c6]Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Camelia Obreja, Alexandru Popa
, Rozica Maria Tache:
Extremal Graphs with Respect to the Modified First Zagreb Connection Index. SYNASC 2018: 141-148 - 2017
- [c5]Guillaume Ducoffe:
Finding Cut-Vertices in the Square Roots of a Graph. WG 2017: 234-248 - 2016
- [c4]Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse:
On the Complexity of Computing Treebreadth. IWOCA 2016: 3-15 - [c3]Guillaume Ducoffe:
The Parallel Complexity of Coloring Games. SAGT 2016: 27-39 - 2015
- [c2]Guillaume Ducoffe, Mathias Lécuyer, Augustin Chaintreau
, Roxana Geambasu:
Web Transparency for Complex Targeting: Algorithms, Limits, and Tradeoffs. SIGMETRICS 2015: 465-466 - 2014
- [c1]Mathias Lécuyer, Guillaume Ducoffe, Francis Lan, Andrei Papancea, Theofilos Petsios, Riley Spahn, Augustin Chaintreau, Roxana Geambasu:
XRay: Enhancing the Web's Transparency with Differential Correlation. USENIX Security Symposium 2014: 49-64
Informal and Other Publications
- 2024
- [i27]Feodor F. Dragan, Guillaume Ducoffe:
ɑi-Metric Graphs: Hyperbolicity. CoRR abs/2404.14792 (2024) - [i26]David Coudert, Mónika Csikós, Guillaume Ducoffe, Laurent Viennot:
Practical Computation of Graph VC-Dimension. CoRR abs/2405.07588 (2024) - 2023
- [i25]Guillaume Ducoffe, Laurent Feuilloley, Michel Habib, François Pitois:
Pattern detection in ordered graphs. CoRR abs/2302.11619 (2023) - [i24]Feodor F. Dragan, Guillaume Ducoffe:
αi-Metric Graphs: Radius, Diameter and all Eccentricities. CoRR abs/2305.02545 (2023) - 2022
- [i23]Guillaume Ducoffe:
Obstructions to faster diameter computation: Asteroidal sets. CoRR abs/2209.12438 (2022) - [i22]Guillaume Ducoffe:
Balancing graph Voronoi diagrams with one more vertex. CoRR abs/2211.03146 (2022) - 2021
- [i21]Guillaume Ducoffe:
Beyond Helly graphs: the diameter problem on absolute retracts. CoRR abs/2101.03574 (2021) - [i20]Feodor F. Dragan, Guillaume Ducoffe, Heather M. Guarnera:
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs. CoRR abs/2102.08349 (2021) - [i19]Pierre Bergé, Guillaume Ducoffe, Michel Habib:
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs. CoRR abs/2110.02709 (2021) - 2020
- [i18]Guillaume Ducoffe:
Eccentricity queries and beyond using Hub Labels. CoRR abs/2010.15794 (2020) - [i17]Guillaume Ducoffe:
Isometric embeddings in trees and their use in the diameter problem. CoRR abs/2010.15803 (2020) - [i16]Guillaume Ducoffe:
Around the diameter of AT-free graphs. CoRR abs/2010.15814 (2020) - [i15]Guillaume Ducoffe:
Distance problems within Helly graphs and k-Helly graphs. CoRR abs/2011.00001 (2020) - [i14]Guillaume Ducoffe:
Optimal diameter computation within bounded clique-width graphs. CoRR abs/2011.08448 (2020) - 2019
- [i13]Guillaume Ducoffe, Michel Habib
, Laurent Viennot:
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. CoRR abs/1907.04385 (2019) - [i12]Guillaume Ducoffe, Michel Habib
, Laurent Viennot:
Fast Diameter Computation within Split Graphs. CoRR abs/1910.03438 (2019) - [i11]Feodor F. Dragan, Guillaume Ducoffe:
A story of diameter, radius and Helly property. CoRR abs/1910.10412 (2019) - 2018
- [i10]Jérémie Chalopin, Victor Chepoi
, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, Yann Vaxès:
Fast approximation and exact computation of negative curvature parameters of graphs. CoRR abs/1803.06324 (2018) - [i9]Guillaume Ducoffe, Alexandru Popa:
A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs. CoRR abs/1804.09393 (2018) - [i8]Guillaume Ducoffe, Alexandru Popa:
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. CoRR abs/1804.09407 (2018) - [i7]Guillaume Ducoffe, Arne Leitert:
Equivalence between pathbreadth and strong pathbreadth. CoRR abs/1809.06041 (2018) - [i6]Guillaume Ducoffe:
Polynomial-time Recognition of 4-Steiner Powers. CoRR abs/1810.02304 (2018) - [i5]Guillaume Ducoffe:
Faster approximation algorithms for computing shortest cycles on weighted graphs. CoRR abs/1810.10229 (2018) - 2017
- [i4]David Coudert, Guillaume Ducoffe, Alexandru Popa:
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. CoRR abs/1707.05016 (2017) - 2016
- [i3]Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse:
On computing tree and path decompositions with metric constraints on the bags. CoRR abs/1601.01958 (2016) - 2014
- [i2]Mathias Lécuyer, Guillaume Ducoffe, Francis Lan, Andrei Papancea, Theofilos Petsios, Riley Spahn, Augustin Chaintreau, Roxana Geambasu:
XRay: Enhancing the Web's Transparency with Differential Correlation. CoRR abs/1407.2323 (2014) - 2012
- [i1]Guillaume Ducoffe, Dorian Mazauric, Augustin Chaintreau:
Convergence of Coloring Games with Collusions. CoRR abs/1212.3782 (2012)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-07-25 20:23 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint