2023
Conference papers
- 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, Jan 2023, Florence, Italy. pp.3654-3663, ⟨10.1137/1.9781611977554.ch139⟩
- DOI
- DOI : 10.1137/1.9781611977554.ch139
- Accès au 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
-
- 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
-
- auteur
- Jean-Claude Bermond, Takako Kodate, Joseph Yu
- titre
- Gossiping with interference in radio ring networks
- article
- 2023
- Accès au texte intégral et 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
-
- 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
-
- 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
-
- 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), pp.187-214. ⟨10.1007/s00373-022-02589-6⟩
- DOI
- DOI : 10.1007/s00373-022-02589-6
- Accès au 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
-
- 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
-
- 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
-
- 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
-
- 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, ⟨10.1145/3486655⟩
- DOI
- DOI : 10.1145/3486655
- Accès au texte intégral et 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
-
- 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
-
- 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
-
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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
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
-
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
-
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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
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
-
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
-
- 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
-
- 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
-
- 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
-
- 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
-
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
-
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
-
- 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
-
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
-
- 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
-
- 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
-
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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
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
-
- 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
-
- 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
- [Research Report] UFC; INRIA; CNRS; Université Côte d’Azur; I3S. 2020
- Accès au texte intégral et 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
-
