Publications of Guillaume Ducoffe
BACK TO COATI PUBLICATION INDEX
Publications of Guillaume Ducoffe
-
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]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On the Complexity of Computing Treebreadth.
Algorithmica,
82(6):1574-1600,
2020.
[WWW
] [PDF
] [bibtex-entry]
-
Daniela Aguirre-Guerrero,
Guillaume Ducoffe,
Lluis Fabrega,
Pere Vila,
and David Coudert.
Low Time Complexity Algorithms for Path Computation in Cayley Graphs.
Discrete Applied Mathematics,
259:218-225,
April 2019.
[WWW
] [PDF
]
Keywords:
interconnection networks,
Cayley graphs,
path computation,
K-shortest paths.
[bibtex-entry]
-
Jean-Claude Bermond,
Augustin Chaintreau,
Guillaume Ducoffe,
and Dorian Mazauric.
How long does it take for all users in a social network to choose their communities?.
Discrete Applied Mathematics,
270:37-57,
2019.
[WWW
] [PDF
]
Keywords:
graphs,
communities,
social networks,
algorithms,
integer partitions,
coloring games.
[bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Alexandru Popa.
P-FPT algorithms for bounded clique-width graphs.
ACM Transactions on Algorithms,
15(3):1-57,
June 2019.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Guillaume Ducoffe,
Nicolas Nisse,
and Karol Suchan.
On interval number in cycle convexity.
Discrete Mathematics and Theoretical Computer Science,
Vol. 20 no. 1(1):1-28,
May 2018.
[WWW
] [PDF
]
Keywords:
convexity,
domination problems in graphs,
interval number,
graph convexity,
complexity,
complexity and algorithms,
dominating set,
graph.
[bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
Nicolas Nisse,
and Mauricio Soto.
On distance-preserving elimination orderings in graphs: Complexity and algorithms.
Discrete Applied Mathematics,
243:140-153,
March 2018.
[WWW
] [PDF
]
Keywords:
bounded treewidth,
integer linear programming,
Keyword: distance-preserving elimination ordering,
metric graph theory,
NP-complete,
exact exponential algorithm.
[bibtex-entry]
-
David Coudert and Guillaume Ducoffe.
Revisiting Decomposition by Clique Separators.
Siam Journal on Discrete Mathematics,
32(1):682 - 694,
January 2018.
[WWW
] [PDF
]
Keywords:
Keyword: clique minimal separator decomposition,
minimal triangulation,
clique-number,
treewidth,
planar graphs,
bounded-degree graphs.
[bibtex-entry]
-
Guillaume Ducoffe.
A short note on the complexity of computing strong pathbreadth.
Information Processing Letters,
133:56-58,
2018.
[WWW
] [PDF
]
Keywords:
NP-complete,
strong pathbreadth,
path decomposition,
acyclic clustering,
graph theory.
[bibtex-entry]
-
Nathann Cohen,
David Coudert,
Guillaume Ducoffe,
and Aurélien Lancin.
Applying clique-decomposition for computing Gromov hyperbolicity.
Theoretical Computer Science,
690:114-139,
2017.
[WWW
] [PDF
]
Keywords:
clique-decomposition,
graph algorithms,
outerplanar graphs,
Gromov hyperbolicity.
[bibtex-entry]
-
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]
-
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]
-
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]
-
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]
-
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]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Treelength of Series-parallel graphs.
In LAGOS 2021 - XI Latin and American Algorithms, Graphs and Optimization Symposium,
São Paulo / Virtual, Brazil,
May 2021.
[WWW
] [PDF
] [bibtex-entry]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Longueur Arborescente des Graphes Série-Parallèles.
In ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
La Rochelle, France,
September 2021.
[WWW
] [PDF
]
Keywords:
décomposition arborescente,
longueur arborescente,
graphes série-parallèles,
sous-graphes isométriques.
[bibtex-entry]
-
Guillaume Ducoffe,
Frédéric Giroire,
Stéphane Pérennes,
and Thibaud Trolliet.
Revisiter l'Attachement Préférentiel, et ses applications aux Réseaux Sociaux.
In ALGOTEL 2020 -- 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Lyon, France,
September 2020.
[WWW
] [PDF
]
Keywords:
Twitter,
Réseaux sociaux,
Graphes aléatoires,
Systèmes complexes,
Attachement préférentiel,
Distribution des degrés,
Chaines de Markov.
[bibtex-entry]
-
Jean-Claude Bermond,
Augustin Chaintreau,
Guillaume Ducoffe,
and Dorian Mazauric.
How long does it take for all users in a social network to choose their communities?.
In 9th International Conference on Fun with Algorithms (FUN 2018),
La Maddalena, Italy,
2018.
[WWW
] [PDF
]
Keywords:
graphs,
communities,
social networks,
integer partitions,
coloring games.
[bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Alexandru Popa.
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs.
In ACM-SIAM Symposium on Discrete Algorithms,
New Orleans, United States,
pages 20,
January 2018.
SIAM.
[WWW
] [PDF
] [bibtex-entry]
-
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]
-
Guillaume Ducoffe,
Ruxandra Marinescu-Ghemeci,
and ALEXANDRU POPA.
On the (di)graphs with (directed) proper connection number two.
In IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS),
volume 62,
Marseille, France,
pages 237 - 242,
September 2017.
[WWW
] [PDF
]
Keywords:
NP-complete,
proper connection,
digraphs,
bipartite,
even dicycles.
[bibtex-entry]
-
Guillaume Ducoffe.
Finding cut-vertices in the square roots of a graph.
In 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017),
volume 10520 of Graph-Theoretic Concepts in Computer Science,
Eindhoven, Netherlands,
pages 234--248,
June 2017.
[WWW
] [PDF
] [bibtex-entry]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Treelength of Series-parallel graphs.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France,
2020.
[WWW
] [PDF
] [bibtex-entry]
-
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:
Fully polynomial FPT,
Graph algorithms,
Hardness in P,
Split decomposition,
Neighbourhood diversity,
Primeval decomposition,
Clique-width,
Modular decomposition.
[bibtex-entry]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
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]
-
G. Ducoffe.
Eulerian and Hamiltonian Directed Hypergraphs.
Technical report RR-7893,
INRIA,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
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: Sat Jan 29 19:00:44 2022
