Publications

Publications HAL du projet ANR. 19-CE48-0013

2024

Journal articles

auteur
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
titre
Digraph redicolouring
article
European Journal of Combinatorics, 2024, 116, pp.103876. ⟨10.1016/j.ejc.2023.103876⟩
DOI
DOI : 10.1016/j.ejc.2023.103876
Accès au texte intégral et bibtex
https://hal.science/hal-04306893/file/Dicolouring_reconfiguration_article-5.pdf BibTex
auteur
Emeric Gioan, Michel Las Vergnas
titre
Computing the fully optimal spanning tree of an ordered bipolar directed graph
article
Discrete Mathematics, In press
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-04387449/file/ABGraphsLP-v27-final-proof-corrections.pdf BibTex
auteur
Pegah Pournajafi, Nicolas Trotignon
titre
Burling graphs revisited, part II: Structure
article
European Journal of Combinatorics, 2024, 116, pp.103849. ⟨10.1016/j.ejc.2023.103849.⟩
DOI
DOI : 10.1016/j.ejc.2023.103849.
Accès au bibtex
https://arxiv.org/pdf/2106.16089 BibTex
auteur
Pegah Pournajafi, Nicolas Trotignon
titre
Burling graphs revisited, part III: Applications to χ -boundedness
article
European Journal of Combinatorics, 2024, 116, pp.103850. ⟨10.1016/j.ejc.2023.103850⟩
DOI
DOI : 10.1016/j.ejc.2023.103850
Accès au bibtex
https://arxiv.org/pdf/2112.11970 BibTex

Conference papers

auteur
Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé
titre
Factoring Pattern-Free Permutations into Separable ones
article
SODA 2024, Jan 2024, Alexandria, United States
Accès au texte intégral et bibtex
https://hal.science/hal-04292977/file/separable-product.pdf BibTex

Preprints, Working Papers, …

auteur
Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta
titre
The 3-dicritical semi-complete digraphs
article
2024
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04471658/file/2402.12014.pdf BibTex
auteur
Florian Hörsch, Lucas Picasarri-Arrieta
titre
Complexity results on the decomposition of a digraph into directed linear forests and out-stars
article
2024
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04471664/file/2401.09202.pdf BibTex
auteur
Lucas Picasarri-Arrieta, Clément Rambaud
titre
Subdivisions in dicritical digraphs with large order or digirth
article
2024
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04471653/file/2401.05938.pdf BibTex

2023

Journal articles

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Finding the k Shortest Simple Paths: Time and Space trade-offs
article
ACM Journal of Experimental Algorithmics, 2023, 28, pp.23. ⟨10.1145/3626567⟩
DOI
DOI : 10.1145/3626567
Accès au texte intégral et bibtex
https://hal.science/hal-03196830/file/JEA-HAL.pdf BibTex
auteur
Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, A. Karolinna Maia, Nicolas Nisse, Ana Silva
titre
On Finding the Best and Worst Orientations for the Metric Dimension
article
Algorithmica, 2023, 85 (10), pp.2962-3002. ⟨10.1007/s00453-023-01132-0⟩
DOI
DOI : 10.1007/s00453-023-01132-0
Accès au texte intégral et bibtex
https://hal.science/hal-04271379/file/metric_dimension.pdf BibTex
auteur
Jean-Claude Bermond, Takako Kodate, Joseph Yu
titre
Gossiping with interference in radio ring networks
article
Discrete Mathematics and Theoretical Computer Science, 2023, 25 (2), pp.#5. ⟨10.46298/dmtcs.9399⟩
DOI
DOI : 10.46298/dmtcs.9399
Accès au texte intégral et bibtex
https://hal.science/hal-04206040/file/BKY-ring-final%20.pdf BibTex
auteur
Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach
titre
Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs
article
The Electronic Journal of Combinatorics, 2023, 30 (1), pp.1-35. ⟨10.37236/10866⟩
DOI
DOI : 10.37236/10866
Accès au texte intégral et bibtex
https://hal.science/hal-04172966/file/unbalanced_spanning_subgraphs_in_edge_labeled_complete_graphs.pdf BibTex
auteur
Edouard Bonnet, Hugues Déprés
titre
Twin-width can be exponential in treewidth
article
Journal of Combinatorial Theory, Series B, 2023
Accès au texte intégral et bibtex
https://hal.science/hal-04292973/file/main.pdf BibTex
auteur
Cláudio Carvalho, Jonas Costa, Raul Lopes, Ana Karolinna Maia, Nicolas Nisse, Cláudia Linhares Sales
titre
From branchings to flows: a study of an Edmonds’ like property to arc-disjoint branching flows
article
Discrete Mathematics and Theoretical Computer Science, In press, vol. 25:1 (10), pp.15. ⟨10.46298/dmtcs.9302⟩
DOI
DOI : 10.46298/dmtcs.9302
Accès au texte intégral et bibtex
https://hal.science/hal-03031759/file/From%20branchings%20to%20flows-dmtcs-episciences.pdf BibTex
auteur
Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne, Théo Pierron
titre
Strengthening a theorem of Meyniel
article
SIAM Journal on Discrete Mathematics, 2023, 37 (2), ⟨10.1137/22M1474394⟩
DOI
DOI : 10.1137/22M1474394
Accès au texte intégral et bibtex
https://hal.science/hal-04156967/file/Kempe_Recoloring.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of series–parallel graphs
article
Discrete Applied Mathematics, 2023, 341, pp.16-30. ⟨10.1016/j.dam.2023.07.022⟩
DOI
DOI : 10.1016/j.dam.2023.07.022
Accès au texte intégral et bibtex
https://hal.science/hal-04268050/file/Series_parallel_graphs_of_treelength_2-4.pdf BibTex
auteur
Lucas Picasarri-Arrieta
titre
Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring
article
Journal of Graph Theory, 2023, ⟨10.1002/jgt.23066⟩
DOI
DOI : 10.1002/jgt.23066
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04337440/file/Brooks_for_digraphs_recolouring___arxiv%20%282%29.pdf BibTex

Conference papers

auteur
Julio Araujo, Frédéric Havet, C. Linhares Sales, Karol Suchan, Nicolas Nisse
titre
Semi-proper orientations of dense graphs
article
LAGOS 2023 6 XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023, Huatulco, Mexico. pp.231-240, ⟨10.1016/j.procs.2023.08.233⟩
DOI
DOI : 10.1016/j.procs.2023.08.233
Accès au texte intégral et bibtex
https://hal.science/hal-04304901/file/Semi_proper_orientation_of_dense_graphs-1.pdf BibTex
auteur
Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva
titre
Deciding the Erdős-Pósa property in 3-connected digraphs
article
WG 2023 – 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg (CH), Switzerland
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04084227/file/Directed_Cylindrical_Grid_and_Models___New_version-6.pdf BibTex
auteur
Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, Mathis Rocton
titre
PACE Solver Description: Touiouidth
article
IPEC 2023 – 18th International Symposium on Parameterized and Exact Computation, Sep 2023, Amsterdam, Netherlands. pp.4, ⟨10.4230/LIPIcs.IPEC.2023.38⟩
DOI
DOI : 10.4230/LIPIcs.IPEC.2023.38
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04395895/file/LIPIcs.IPEC.2023.38.pdf BibTex
auteur
Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht
titre
Kernelization for Graph Packing Problems via Rainbow Matching
article
SODA 2023 – ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Jan 2023, Florence, Italy. pp.3654-3663, ⟨10.1137/1.9781611977554.ch139⟩
DOI
DOI : 10.1137/1.9781611977554.ch139
Accès au texte intégral et bibtex
https://hal.science/hal-04042995/file/2207.06874.pdf BibTex
auteur
Edouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek
titre
Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 cup C_4
article
ESA 2023, Sep 2023, Amsterdam, Netherlands
Accès au texte intégral et bibtex
https://hal.science/hal-04292975/file/mis-ind-minor.pdf BibTex
auteur
Édouard Bonnet, Julien Duron
titre
Stretch-width
article
IPEC 2023, Sep 2023, Amsterdam, Netherlands
Accès au texte intégral et bibtex
https://hal.science/hal-04292981/file/stretch-width.pdf BibTex
auteur
Edouard Bonnet, Dibyayan Chakraborty, Julien Duron
titre
Cutting Barnette graphs perfectly is hard
article
WG 2023, Jun 2023, Fribourg (Germany), Germany
Accès au texte intégral et bibtex
https://hal.science/hal-04292961/file/arxiv.pdf BibTex
auteur
Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud
titre
On the minimum number of inversions to make a digraph k-(arc-)strong
article
EUROCOMB 2023 – European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.386-392, ⟨10.5817/CZ.MUNI.EUROCOMB23-054⟩
DOI
DOI : 10.5817/CZ.MUNI.EUROCOMB23-054
Accès au texte intégral et bibtex
https://hal.science/hal-04352250/file/Strong_inversion.pdf BibTex
auteur
Colin Geniet, Stéphan Thomassé
titre
First Order Logic and Twin-Width in Tournaments
article
31st Annual European Symposium on Algorithms (ESA 2023), Sep 2023, Amsterdam, Netherlands. pp.53:1–53:14, ⟨10.4230/LIPIcs.ESA.2023.53⟩
DOI
DOI : 10.4230/LIPIcs.ESA.2023.53
Accès au texte intégral et bibtex
https://hal.science/hal-04249625/file/LIPIcs-ESA-2023-53.pdf BibTex
auteur
Frédéric Havet, Lucas Picasarri-Arrieta, Clément Rambaud
titre
On the Minimum Number of Arcs in 4-Dicritical Oriented Graphs
article
WG 2023 – International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg, Switzerland. pp.376-387, ⟨10.1007/978-3-031-43380-1_27⟩
DOI
DOI : 10.1007/978-3-031-43380-1_27
Accès au texte intégral et bibtex
https://hal.science/hal-04352253/file/4_dicritical_journal_version.pdf BibTex
auteur
Lucas Picasarri-Arrieta
titre
Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring
article
Eurocomb 2023 – 12th European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.760-765, ⟨10.5817/CZ.MUNI.EUROCOMB23-105⟩
DOI
DOI : 10.5817/CZ.MUNI.EUROCOMB23-105
Accès au texte intégral et bibtex
https://hal.science/hal-04204446/file/2301.04881 BibTex

Reports

auteur
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
titre
Digraph redicolouring
article
Inria. 2023
Accès au texte intégral et bibtex
https://hal.science/hal-04281467/file/2301.03417.pdf BibTex
auteur
Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau
titre
Redicolouring digraphs: directed treewidth and cycle-degeneracy
article
Inria. 2023
Accès au texte intégral et bibtex
https://hal.science/hal-04271445/file/2307.06700.pdf BibTex

Preprints, Working Papers, …

auteur
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Stéphan Thomassé
titre
( #» P 6 , triangle)-free digraphs have bounded dichromatic number
article
2023
Accès au texte intégral et bibtex
https://hal.science/hal-03985871/file/2212.02272.pdf BibTex
auteur
Pierre Aboulker, Thomas Bellitto, Frédéric Havet, Clément Rambaud
titre
On the minimum number of arcs in k-dicritical oriented graphs
article
2023
Accès au texte intégral et bibtex
https://hal.science/hal-03985818/file/2022_number_of_arcs_in_3_dicritical_oriented_graphs.pdf BibTex
auteur
Stéphane Bessy, Jørgen Bang-Jensen, Lucas Picasarri-Arrieta
titre
Constrained Flows in Networks
article
2023
Accès au bibtex
https://arxiv.org/pdf/2310.01042 BibTex
auteur
Stéphane Bessy, Frédéric Havet, Lucas Picasarri-Arrieta
titre
Dichromatic number of chordal graphs
article
2023
Accès au bibtex
https://arxiv.org/pdf/2309.17385 BibTex
auteur
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Kunihiro Wasa
titre
On the hardness of inclusion-wise minimal separators enumeration
article
2023
DOI
DOI : 10.1016/j.ipl.2023.106469
Accès au texte intégral et bibtex
https://hal.science/hal-04216381/file/2308.15444.pdf BibTex
auteur
Lucas Picasarri-Arrieta, Michael Stiebitz
titre
Minimum number of arcs in $k$-critical digraphs with order at most k-1$
article
2023
Accès au bibtex
https://arxiv.org/pdf/2310.03584 BibTex

2022

Journal articles

auteur
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković
titre
Graphs with polynomially many minimal separators
article
Journal of Combinatorial Theory, Series B, 2022, 152, pp.248-280. ⟨10.1016/j.jctb.2021.10.003⟩
DOI
DOI : 10.1016/j.jctb.2021.10.003
Accès au bibtex
https://arxiv.org/pdf/2005.05042 BibTex
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta
titre
Complexity of some arc-partition problems for digraphs
article
Theoretical Computer Science, 2022, 928, pp.167-182. ⟨10.1016/j.tcs.2022.06.023⟩
DOI
DOI : 10.1016/j.tcs.2022.06.023
Accès au texte intégral et bibtex
https://hal.science/hal-03699980/file/TCSnewfinal.pdf BibTex
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo
titre
Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
article
Journal of Graph Theory, 2022, 100 (2), pp.294-314. ⟨10.1002/jgt.22779⟩
DOI
DOI : 10.1002/jgt.22779
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-04032263/file/jgt.22779.pdf BibTex
auteur
Jørgen Bang-Jensen, Frédéric Havet, Matthias Kriesell, A. Yeo
titre
Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
article
Journal of Graph Theory, 2022, 99 (4), pp.615-636. ⟨10.1002/jgt.22755⟩
DOI
DOI : 10.1002/jgt.22755
Accès au bibtex
https://arxiv.org/pdf/2008.05272 BibTex
auteur
Jørgen Bang-Jensen, Stéphane Bessy, Anders Yeo
titre
Non-separating Spanning Trees and Out-Branchings in Digraphs of Independence Number 2
article
Graphs and Combinatorics, 2022, 38 (6), ⟨10.1007/s00373-022-02589-6⟩
DOI
DOI : 10.1007/s00373-022-02589-6
Accès au texte intégral et bibtex
https://hal.science/hal-04032270/file/2007.02834.pdf BibTex
auteur
Julien Bensmail, Fionn Mc Inerney, Nicolas Nisse
titre
Metric Dimension: from Graphs to Oriented Graphs
article
Discrete Applied Mathematics, 2022, 323, pp.28-42. ⟨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://inria.hal.science/hal-01938290/file/ori_md_DAM_version_HAL.pdf BibTex
auteur
Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach
titre
Factorially Many Maximum Matchings Close to the Erdős-Gallai Bound
article
The Electronic Journal of Combinatorics, 2022, 29 (2), ⟨10.37236/10610⟩
DOI
DOI : 10.37236/10610
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03701284/file/factiorally_many_maximum_matchings.pdf BibTex
auteur
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width II: small classes
article
Combinatorial Theory, 2022, 2 (2), ⟨10.5070/C62257876⟩
DOI
DOI : 10.5070/C62257876
Accès au bibtex
https://arxiv.org/pdf/2006.09877 BibTex
auteur
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width II: small classes
article
Combinatorial Theory, 2022, ⟨10.5070/C62257876⟩
DOI
DOI : 10.5070/C62257876
Accès au texte intégral et bibtex
https://hal.science/hal-03750978/file/twinwidthII.pdf BibTex
auteur
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width I: tractable FO model checking
article
Journal of the ACM (JACM), 2022, 69 (1), pp.1-46. ⟨10.1145/3486655⟩
DOI
DOI : 10.1145/3486655
Accès au texte intégral et bibtex
https://hal.science/hal-03750975/file/arxiv1v3.pdf BibTex
auteur
Edouard Bonnet
titre
4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^{4/3}
article
ACM Transactions on Algorithms, 2022, 18 (2), ⟨10.1145/3494540⟩
DOI
DOI : 10.1145/3494540
Accès au texte intégral et bibtex
https://hal.science/hal-03750993/file/arxiv2.pdf BibTex
auteur
Emeric Gioan
titre
On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids
article
Discrete Mathematics, 2022, 345 (7), pp.#112796. ⟨10.1016/j.disc.2022.112796⟩
DOI
DOI : 10.1016/j.disc.2022.112796
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
Frédéric Giroire, Nicolas Nisse, Thibaud Trolliet, Małgorzata Sulkowska
titre
Preferential Attachment Hypergraph with High Modularity
article
Network Science, 2022, 10 (4), pp.400-429. ⟨10.1017/nws.2022.35⟩
DOI
DOI : 10.1017/nws.2022.35
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04044811/file/PREFERENTIAL%20ATTACHMENT%20HYPERGRAPH%20WITH%20HIGH%20MODULARITY.pdf BibTex
auteur
Pierre Monmarché, Mouad Ramil
titre
Overdamped limit at stationarity for non-equilibrium Langevin diffusions
article
Electronic Communications in Probability, 2022, 27 (none), ⟨10.1214/22-ecp447⟩
DOI
DOI : 10.1214/22-ecp447
Accès au texte intégral et bibtex
https://hal.sorbonne-universite.fr/hal-03549666/file/22-ECP447.pdf BibTex

Conference papers

auteur
Pierre Bergé, Édouard Bonnet, Hugues Déprés
titre
Deciding twin-width at most 4 is NP-complete
article
49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.18⟩
DOI
DOI : 10.4230/LIPIcs.ICALP.2022.18
Accès au texte intégral et bibtex
https://hal.science/hal-03750997/file/camera.pdf BibTex
auteur
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk
titre
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
article
37th Annual ACM/IEEE Symposium on Logic in Computer Science ( LICS 2022 ), Aug 2022, Haifa, Israel. ⟨10.1145/3531130.3533367⟩
DOI
DOI : 10.1145/3531130.3533367
Accès au texte intégral et bibtex
https://hal.science/hal-03751012/file/arxiv.pdf BibTex
auteur
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Toruńczyk
titre
Twin-width IV: ordered graphs and matrices
article
STOC 2022, Jun 2022, Rome, Italy
Accès au texte intégral et bibtex
https://hal.science/hal-03714452/file/main-STOC.pdf BibTex
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.science/hal-03430581/file/main.pdf BibTex
auteur
Thomas Dissaux, Nicolas Nisse
titre
Pathlength of Outerplanar graphs
article
LATIN 2022 – 15th Latin American Theoretical Informatics Symposium, Nov 2022, Guanajuato, Mexico. pp.172-187, ⟨10.1007/978-3-031-20624-5_11⟩
DOI
DOI : 10.1007/978-3-031-20624-5_11
Accès au texte intégral et bibtex
https://hal.science/hal-03895318/file/Pathlength_Outerplanar-1.pdf BibTex
auteur
Emeric Gioan
titre
On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives
article
ICGT 2022 – 11th International Colloquium on Graph Theory and Combinatorics, Jul 2022, Montpellier, France
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-03868791/file/ICGT_2022_paper_73.pdf BibTex

Reports

auteur
Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, Karol Suchan
titre
Semi-proper orientations of dense graphs
article
Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2022
Accès au texte intégral et bibtex
https://hal.science/hal-03907202/file/Semi-proper-chordal.pdf BibTex

Preprints, Working Papers, …

auteur
Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore, Théo Pierron
titre
Recolouring planar graphs of girth at least five
article
2022
Accès au texte intégral et bibtex
https://hal.science/hal-03773048/file/Recoloring_Planar_graphs_of_large_girth.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, 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.science/hal-03367072/file/Main-1.pdf BibTex
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, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
DOI
DOI : 10.1016/j.ejc.2021.103394
Accès au bibtex
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, 2021, 96 (4), pp.594-618. ⟨10.1002/jgt.22633⟩
DOI
DOI : 10.1002/jgt.22633
Accès au bibtex
BibTex
auteur
Julien Bensmail, Bi Li, Binlong Li, Nicolas Nisse
titre
On Minimizing the Maximum Color for the 1-2-3 Conjecture
article
Discrete Applied Mathematics, 2021, 289, pp.32-51. ⟨10.1016/j.dam.2020.09.020⟩
DOI
DOI : 10.1016/j.dam.2020.09.020
Accès au texte intégral et bibtex
https://hal.science/hal-02330418/file/maxWeightIndirectColoring_revised.pdf 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, 2021, 83 (5), pp.1393-1420. ⟨10.1007/s00453-020-00788-2⟩
DOI
DOI : 10.1007/s00453-020-00788-2
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-03271568/file/LIPIcs-MFCS-2019-27.pdf BibTex
auteur
Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, Stéphan Thomassé
titre
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
article
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
DOI
DOI : 10.1145/3433160
Accès au texte intégral et bibtex
https://hal.science/hal-03107441/file/arxiv.pdf BibTex
auteur
Ali Dehghan, Frédéric Havet
titre
On the semi-proper orientations of graphs
article
Discrete Applied Mathematics, 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://inria.hal.science/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, 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
DOI
DOI : 10.1017/S0963548321000067
Accès au texte intégral et bibtex
https://inria.hal.science/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, 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://inria.hal.science/hal-03269226/file/unavoidability-revise2.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, 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.science/hal-03060185/file/1912.00516.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, 2021, ⟨10.1002/jgt.22666⟩
DOI
DOI : 10.1002/jgt.22666
Accès au texte intégral et bibtex
https://hal.science/hal-03255154/file/TTF-EHF-Part-1-V3.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, 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.science/hal-03255160/file/TTF-EHF-Part-2-V2.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.science/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
ACM-SIAM Symposium on Discrete Algorithms (SODA21), Jan 2021, Alexandria, United States
Accès au texte intégral et bibtex
https://hal.science/hal-03107577/file/SODA21%20-%20487%20%281%29.pdf BibTex
auteur
Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
titre
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
article
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.35⟩
DOI
DOI : 10.4230/LIPIcs.ICALP.2021.35
Accès au texte intégral et bibtex
https://hal.science/hal-03107571/file/tww3Icalp.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.science/hal-03430542/file/main.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.science/hal-03430322/file/finalICALP.pdf 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.science/hal-03430313/file/finalSTACS.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of Series-parallel graphs
article
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⟩
DOI
DOI : 10.1016/j.procs.2021.11.008
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03175837/file/Lagos_2021%289%29.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://inria.hal.science/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
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.science/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.science/hal-03264788/file/Multimod_kssp_Hal.pdf BibTex
auteur
Frédéric Havet, Jørgen Bang-Jensen, Anders Yeo
titre
Spanning eulerian subdigraphs in semicomplete digraphs
article
[Research Report] Inria; CNRS; I3S; Université côte d’azur. 2021
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03472923/file/supereulerian-revise.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.science/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.science/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, 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
Julien Bensmail, François Dross, Nicolas Nisse
titre
Decomposing degenerate graphs into locally irregular subgraphs
article
Graphs and Combinatorics, 2020, 36 (6), pp.1869-1889. ⟨10.1007/s00373-020-02193-6⟩
DOI
DOI : 10.1007/s00373-020-02193-6
Accès au texte intégral et bibtex
https://hal.science/hal-02090804/file/irregular-degenerate.pdf BibTex
auteur
Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
titre
On the complexity of colouring antiprismatic graphs
article
Algorithmica, 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, 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.science/hal-03060183/file/1707.04205.pdf BibTex

Conference papers

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://inria.hal.science/hal-02835953/file/algotel-FinalVersion.pdf BibTex
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://inria.hal.science/hal-02865918/file/LIPIcs-SEA-2020-18.pdf BibTex
auteur
Jørgen Bang-Jensen, Jonas Costa 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://inria.hal.science/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.science/hal-03430381/file/main.pdf 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.science/hal-03430494/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 texte intégral et bibtex
https://hal.science/hal-03107581/file/twinwidthfocsRevised.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://inria.hal.science/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.science/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.science/hal-02921466/file/oriented-md.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.science/hal-03010346/file/Lagos_2021.pdf BibTex

Les commentaires sont clos.