Publications

Publications HAL du projet ANR. 19-CE48-0013

2022

Conference papers

auteur
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé
titre
Twin-width VI: the lens of contraction sequences
article
SODA 2022, Jan 2022, Alexandria, United States
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430581/file/main.pdf BibTex

2021

Journal articles

auteur
Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
titre
On the tree-width of even-hole-free graphs
article
European Journal of Combinatorics, Elsevier, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
DOI
DOI : 10.1016/j.ejc.2021.103394
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03367072/file/Main-1.pdf BibTex
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Jing Huang, Matthias Kriesell
titre
Good orientations of unions of edge‐disjoint spanning trees
article
Journal of Graph Theory, Wiley, 2021, 96 (4), pp.594-618. ⟨10.1002/jgt.22633⟩
DOI
DOI : 10.1002/jgt.22633
Accès au bibtex
BibTex
auteur
Stéphane Bessy, Marin Bougeret, Ramaswamy Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, Meirav Zehavi
titre
Packing Arc-Disjoint Cycles in Tournaments
article
Algorithmica, Springer Verlag, 2021, 83 (5), pp.1393-1420. ⟨10.1007/s00453-020-00788-2⟩
DOI
DOI : 10.1007/s00453-020-00788-2
Accès au bibtex
BibTex
auteur
Ali Dehghan, Frédéric Havet
titre
On the semi-proper orientations of graphs
article
Discrete Applied Mathematics, Elsevier, 2021, 296, pp.9-25. ⟨10.1016/j.dam.2020.07.003⟩
DOI
DOI : 10.1016/j.dam.2020.07.003
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03035385/file/semi-proper.pdf BibTex
auteur
Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia, Alex Scott, Benny Sudakov
titre
Powers of paths in tournaments
article
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
DOI
DOI : 10.1017/S0963548321000067
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03269230/file/powers-of-path-tournaments.pdf BibTex
auteur
François Dross, Frédéric Havet
titre
On the unavoidability of oriented trees
article
Journal of Combinatorial Theory, Series B, Elsevier, 2021, 151, pp.83-110. ⟨10.1016/j.jctb.2021.06.003⟩
DOI
DOI : 10.1016/j.jctb.2021.06.003
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03269226/file/unavoidability-revise2.pdf BibTex
auteur
Emeric Gioan
titre
On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids
article
Discrete Mathematics, Elsevier, In press
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-03269872/file/Tutte-Expansions-Perspectives-v10-revision%20review2.pdf BibTex
auteur
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
titre
The (theta, wheel)-free graphs Part IV: Induced paths and cycles
article
Journal of Combinatorial Theory, Series B, Elsevier, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
DOI
DOI : 10.1016/j.jctb.2020.06.002
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03060185/file/1912.00516.pdf BibTex
auteur
Ni Luh Dewi Sintiari, Marcin Pilipczuk, Stéphan Thomassé, Nicolas Trotignon
titre
(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
article
Journal of Graph Theory, Wiley, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩
DOI
DOI : 10.1002/jgt.22675
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03255160/file/TTF-EHF-Part-2-V2.pdf BibTex
auteur
Ni Luh Dewi Sintiari, Nicolas Trotignon
titre
(Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
article
Journal of Graph Theory, Wiley, 2021, ⟨10.1002/jgt.22666⟩
DOI
DOI : 10.1002/jgt.22666
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03255154/file/TTF-EHF-Part-1-V3.pdf BibTex

Conference papers

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
De la difficulté de trouver des chemins dissimilaires
article
ALGOTEL 2021 – 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03219987/file/On_the_k_top_shortest_paths_with_diversity_constraints_c.pdf BibTex
auteur
Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width II: small classes
article
SODA 2021, Jan 2021, Alexandria, United States
Accès au bibtex
https://arxiv.org/pdf/2006.09877 BibTex
auteur
Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width III: Max Independent Set and Coloring
article
ICALP 2021, Jul 2021, Glasgow, United Kingdom
Accès au bibtex
https://arxiv.org/pdf/2007.14161 BibTex
auteur
Édouard Bonnet
titre
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
article
STACS 2021, Mar 2021, Saarbrücken, Germany. ⟨10.4230/LIPIcs.STACS.2021.47⟩
DOI
DOI : 10.4230/LIPIcs.STACS.2021.47
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430313/file/finalSTACS.pdf BibTex
auteur
Édouard Bonnet
titre
4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3
article
ICALP 2021, Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.24⟩
DOI
DOI : 10.4230/LIPIcs.ICALP.2021.24
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430322/file/finalICALP.pdf BibTex
auteur
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width and polynomial kernels
article
IPEC 2021, Sep 2021, Lisbon, Portugal
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430542/file/main.pdf BibTex

Book sections

auteur
Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud
titre
On the dichromatic number of surfaces
article
Extended Abstracts EuroComb 2021, 14, Springer International Publishing, pp.181-187, 2021, Trends in Mathematics, ⟨10.1007/978-3-030-83823-2_29⟩
DOI
DOI : 10.1007/978-3-030-83823-2_29
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03424140/file/dichromatic-eurocomb.pdf BibTex

Reports

auteur
Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud
titre
On the dichromatic number of surfaces
article
[Research Report] Inria; CNRS; I3S; Université Côte D’Azur. 2021
Accès au bibtex
https://arxiv.org/pdf/2102.01034 BibTex
auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Finding the k Shortest Simple Paths: Time and Space trade-offs
article
[Research Report] Inria; I3S, Université Côte d’Azur. 2021
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03196830/file/Journal-kssp.pdf BibTex
auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
On the complexity of finding $k$ shortest dissimilar paths in a graph
article
[Research Report] Inria; CNRS; I3S; Université Côte d’Azur. 2021, pp.9
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03187276/file/On_the_k_top_shortest_paths_with_dissimilarity_constraints-v2.pdf BibTex
auteur
David Coudert, Ali Al Zoobi, Arthur Finkelstein
titre
On finding $k$ earliest arrival time journeys in public transit networks
article
[Research Report] Inria. 2021
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03264788/file/Multimod_kssp_Hal.pdf BibTex

Software

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
k shortest simple paths
article
2021, ⟨swh:1:dir:4dc5b3b01ddcd9091dd5a628916638a1cefd8e0c;origin=https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths/;visit=swh:1:snp:f0cc7e5f3ec6200d39061db55146a7ab340fee95;anchor=swh:1:rev:124c172d617e485a6b3cd5dc6db7768d86a3a5af⟩
Accès au bibtex
BibTex

Preprints, Working Papers, …

auteur
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković
titre
Maximum independent sets in (pyramid, even hole)-free graphs
article
2021
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02424059/file/1912.11246.pdf BibTex
auteur
Louis Esperet, Nicolas Trotignon
titre
Coloring graphs with no induced subdivision of $K_4^+$
article
2021
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03092640/file/1901.04170.pdf BibTex

2020

Journal articles

auteur
Noga Alon, Jørgen Bang‐jensen, Stéphane Bessy
titre
Out‐colourings of digraphs
article
Journal of Graph Theory, Wiley, 2020, 93 (1), pp.88-112. ⟨10.1002/jgt.22476⟩
DOI
DOI : 10.1002/jgt.22476
Accès au bibtex
https://arxiv.org/pdf/1706.06441 BibTex
auteur
Fionn Mc Inerney, Julien Bensmail, Nicolas Nisse
titre
Metric Dimension: from Graphs to Oriented Graphs
article
Discrete Applied Mathematics, Elsevier, In press, ⟨10.1016/j.dam.2020.09.013⟩
DOI
DOI : 10.1016/j.dam.2020.09.013
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01938290/file/ori_md_DAM_version_HAL.pdf BibTex
auteur
Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
titre
On the complexity of colouring antiprismatic graphs
article
Algorithmica, Springer Verlag, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩
DOI
DOI : 10.1007/s00453-020-00767-7
Accès au bibtex
https://arxiv.org/pdf/1910.11001 BibTex
auteur
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
titre
The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring
article
Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩
DOI
DOI : 10.1016/j.jctb.2019.07.003
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03060183/file/1707.04205.pdf BibTex

Conference papers

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Space and Time Trade-Off for the k Shortest Simple Paths Problem
article
SEA 2020 – 18th International Symposium on Experimental Algorithms, Jun 2020, Catania, Italy. pp.13, ⟨10.4230/LIPIcs.SEA.2020.18⟩
DOI
DOI : 10.4230/LIPIcs.SEA.2020.18
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02865918/file/LIPIcs-SEA-2020-18.pdf BibTex
auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Compromis espace-temps pour le problème de k plus courts chemins simples
article
ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. pp.4
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02835953/file/algotel-FinalVersion.pdf BibTex
auteur
Jørgen Bang-Jensen, Jonas Ferreira da Silva, Frédéric Havet
titre
Inversion number of an oriented graph and related parameters
article
ALGOS 2020 – 1st International Conference on Algebras, Graphs and Ordered Sets, Aug 2020, Nancy / Virtual, France
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03035419/file/inversion-ALGOS.pdf BibTex
auteur
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-Joung Kwon
titre
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
article
IPEC 2020, Dec 2020, Hong Kong, China
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430381/file/main.pdf BibTex
auteur
Edouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width I: tractable FO model checking
article
FOCS 2020, Nov 2020, online, United States
Accès au bibtex
https://arxiv.org/pdf/2004.14789 BibTex
auteur
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
titre
Maximum Clique in Disk-Like Intersection Graphs
article
FSTTCS 2020, Dec 2020, Goa, India
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03430494/file/main.pdf BibTex
auteur
Thibaud Trolliet, Nathann Cohen, Frédéric Giroire, Luc Hogie, Stéphane Pérennes
titre
Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter
article
COMPLEX NETWORKS 2020 – 9th International Conference on Complex Networks and their Applications, Dec 2020, Madrid / Virtual, Spain
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03052083/file/ICC___ComplexNet___Submission_version.pdf BibTex

Reports

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Space and time trade-off for the k shortest simple paths problem
article
[Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02465317/file/HAL_kSSP.pdf BibTex
auteur
Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Ana Karolinna Maia de Oliviera, Nicolas Nisse, Ana Silva
titre
On finding the best and worst orientations for the metric dimension
article
[Research Report] Inria. 2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02921466/file/oriented-md.pdf BibTex
auteur
Cláudio Carvalho, Jonas Costa, Cláudia Sales, Raul Lopes, Ana Karolinna Maia de Oliveira, Nicolas Nisse
titre
On the characterization of networks with multiple arc-disjoint branching flows
article
[Research Report] UFC; INRIA; CNRS; Université Côte d’Azur; I3S; LIRMM; Université de Montpellier. 2020
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03031759/file/Conjecture_results.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of Series-parallel graphs
article
[Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03010346/file/Lagos_2021.pdf BibTex

Les commentaires sont clos.