Page d'accueil > Recherche > Equipes > ALGCO

ALGCO: Algorithmes, Graphes et Combinatoire

Les recherches de l’équipe AlGCo se concentrent sur l’étude théorique et algorithmique de structures combinatoires classiques : principalement les graphes, mais aussi les graphes orientés, matroïdes et matroïdes orientés. Nos motivations sont d’ordre fondamental (questions de partitionnement, coloration, plongement, isomorphisme), algorithmique (notamment autour de la complexité paramétrée : algorithmes FPT, existence de noyau polynomiaux) ou applicatif, en provenance d’autres domaines de l’informatique théorique (bio-informatique, imagerie, morphométrie, modélisation de réseaux...).

Membres

Permanents

Stephane Bessy, Maître de Conférences UM
Marin Bougeret, Maître de Conférences UM
Emeric Gioan, Chargé de Recherche CNRS
Daniel Gonçalves, Chargé de Recherche CNRS
Philippe Janssen, Maître de Conférences UM
Mickael Montassier, Professeur des Universités UM
Pascal Ochem, Chargé de Recherche CNRS
Christophe Paul, Directeur de Recherche CNRS
Alexandre Pinlou, Professeur des Universités UM
Ignasi Sau, Chargé de Recherche CNRS
Geneviève Simonet, Maître de Conférences UM
Dimitrios Thilikos Touloupas, Directeur de Recherche CNRS

Non permanents

Aniket Basu Roy, CDD Chercheur CNRS
Lucas Isenmann, Doctorant
Mohammed Senhaji, CDD Enseignant-Chercheur UM
Abhijat Sharma, Doctorant CNRS
Jocelyn Thiebaut, Doctorant
Petru Valicov, Invité longue durée, Maître de Conférences UM

Publications depuis 2014 - Evaluation 2019

Articles de revues internationales

2019

On the Kőnig-Egerváry theorem for k-paths
Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

Journal of Graph Theory, Wiley, 2019, 91 (1), pp.73-87. ⟨10.1002/jgt.22421⟩. ⟨lirmm-02078255⟩.
On the number of circuit–cocircuit reversal classes of an oriented matroid
Emeric Gioan, Chi Ho Yuen

Discrete Mathematics, Elsevier, 2019, 342 (4), pp.1056-1059. ⟨10.1016/j.disc.2018.12.006⟩. ⟨lirmm-01996159⟩.
A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
François Dross, Mickael Montassier, Alexandre Pinlou

Discrete Mathematics, Elsevier, 2019, 342 (4), pp.943-950. ⟨10.1016/j.disc.2018.11.023⟩. ⟨lirmm-02010775⟩.
The active bijection for graphs
Emeric Gioan, Michel Las Vergnas

Advances in Applied Mathematics, Elsevier, 2019, 104, pp.165-236. ⟨10.1016/j.aam.2018.11.001⟩. ⟨lirmm-01996135⟩.
Large induced forests in planar graphs with girth 4
François Dross, Mickaël Montassier, Alexandre Pinlou

Discrete Applied Mathematics, Elsevier, 2019, 254, pp.96-106. ⟨10.1016/j.dam.2018.06.029⟩. ⟨lirmm-02021020⟩.
On some interesting ternary formulas
Pascal Ochem, Matthieu Rosenfeld

Electronic Journal of Combinatories, 2019, 26 (1), pp.P1.12. ⟨lirmm-02083616⟩.
Strong immersion is a well-quasi-ordering for semicomplete digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk

Journal of Graph Theory, Wiley, 2019, 90, pp.484-496. ⟨10.1002/jgt.22408⟩. ⟨lirmm-01918986⟩.
Oriented incidence colourings of digraphs
Christopher Duffy, Gary Macgillivray, Pascal Ochem, André Raspaud

Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2019, 39 (1), pp.191-210. ⟨10.7151/dmgt.2076⟩. ⟨lirmm-02011333⟩.
Degree-constrained 2-partitions of graphs
Jørgen Bang-Jensen, Stéphane Bessy

Theoretical Computer Science, Elsevier, In press, ⟨10.1016/j.tcs.2018.12.023⟩. ⟨lirmm-02011257⟩. <10.1016/j.tcs.2018.12.023>

2018

Approximability and exact resolution of the multidimensional binary vector assignment problem
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau

Journal of Combinatorial Optimization, Springer Verlag, 2018, 36 (3), pp.1059-1073. ⟨10.1007/s10878-018-0276-8⟩. ⟨lirmm-01922494⟩.
Complexity dichotomies for the Minimum F -Overlay problem
Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant

Journal of Discrete Algorithms, Elsevier, 2018, 52-53, pp.133-142. ⟨10.1016/j.jda.2018.11.010⟩. ⟨hal-01947563⟩.
Robust scheduling with budgeted uncertainty
Marin Bougeret, Artur Alves Pessoa, Michael Poss

Discrete Applied Mathematics, Elsevier, 2018, 261 (31), pp.93-107. ⟨10.1016/j.dam.2018.07.001⟩. ⟨lirmm-02020566⟩.
Structure and Enumeration of $K4$-minor-free links and link diagrams
Juanjo Rué, Dimitrios M. Thilikos, Vasiliki Velona

Electronic Notes in Discrete Mathematics, Elsevier, 2018, 68, pp.119-124. ⟨10.1016/j.endm.2018.06.021⟩. ⟨lirmm-01890505⟩.
On triangles in $Kr$-minor free graphs
Boris Albar, Daniel Gonçalves

Journal of Graph Theory, Wiley, 2018, 88 (1), pp.154-173. ⟨10.1002/jgt.22203⟩. ⟨lirmm-01888027⟩.
Induced minors and well-quasi-ordering
Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

Journal of Combinatorial Theory, Series B, Elsevier, 2018, ⟨10.1016/j.jctb.2018.05.005⟩. ⟨hal-01813903⟩. <10.1016/j.jctb.2018.05.005>
An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

Algorithmica, Springer Verlag, 2018, 80 (4), pp.1330-1356. ⟨10.1007/s00453-017-0313-5⟩. ⟨lirmm-01609998⟩.
Out-degree reducing partitions of digraphs
Joergen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo

Theoretical Computer Science, Elsevier, 2018, 719, pp.64-72. ⟨10.1016/j.tcs.2017.11.007⟩. ⟨hal-01765642⟩.
Degenerate matchings and edge colorings
Julien Baste, Dieter Rautenbach

Discrete Applied Mathematics, Elsevier, 2018, 239, pp.38-44. ⟨10.1016/j.dam.2018.01.002⟩. ⟨hal-01777928⟩.
Cutwidth: Obstructions and Algorithmic Aspects
Archontia Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Algorithmica, Springer Verlag, 2018, ⟨10.1007/s00453-018-0424-7⟩. ⟨hal-01814167⟩. <10.1007/s00453-018-0424-7>
Improved FPT algorithms for weighted independent set in bull-free graphs
Henri Perret Du Cray, Ignasi Sau

Discrete Mathematics, Elsevier, 2018, 341 (2), pp.451-462. ⟨10.1016/j.disc.2017.09.012⟩. ⟨hal-01733496⟩.
Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos

ACM Transactions on Algorithms, Association for Computing Machinery, 2018, 14 (1), pp.1-31. ⟨10.1145/3155298⟩. ⟨lirmm-01890563⟩.
Hitting minors, subdivisions, and immersions in tournaments
Jean-Florent Raymond

Discrete Mathematics and Theoretical Computer Science, DMTCS, 2018, 20 (1), pp.4212. ⟨https://dmtcs.episciences.org/4212⟩. ⟨10.23638/DMTCS-20-1-5⟩. ⟨hal-01814499⟩.
Multicut Is FPT
Nicolas Bousquet, Jean Daligault, Stéphan Thomassé

SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2018, 47 (1), pp.166-207. ⟨10.1137/140961808⟩. ⟨hal-01804120⟩.
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?
Marin Bougeret, Ignasi Sau

Algorithmica, Springer Verlag, 2018, ⟨10.1007/s00453-018-0468-8⟩. ⟨lirmm-02020500⟩. <10.1007/s00453-018-0468-8>
An FPT 2-Approximation for Tree-Cut Decomposition
Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Algorithmica, Springer Verlag, 2018, 80 (1), pp.116-135. ⟨10.1007/s00453-016-0245-5⟩. ⟨hal-01690385⟩.
On repetition thresholds of caterpillars and trees of bounded degree
Borut Lužar, Pascal Ochem, Alexandre Pinlou

The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (1), pp.#P1.61. ⟨lirmm-01730276⟩.
Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree
François Dross, Mickaël Montassier, Alexandre Pinlou

The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (1), pp.#P1.45. ⟨http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45⟩. ⟨lirmm-01730269⟩.
A Tight Erdös-Pósa Function for Wheel Minors
Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwénaël Joret, Jean-Florent Raymond, Ignasi Sau

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (3), pp.2302-2312. ⟨10.1137/17M1153169⟩. ⟨hal-01995696⟩.
The Geodetic Hull Number is Hard for Chordal Graphs
Stéphane Bessy, Mitre Dourado, Lucia Penso, Dieter Rautenbach

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.543-547. ⟨10.1137/17M1131726⟩. ⟨lirmm-01997429⟩.
Avoidability of circular formulas
Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold

Theoretical Computer Science, Elsevier, 2018, 726, pp.1-4. ⟨10.1016/j.tcs.2017.11.014⟩. ⟨lirmm-01692716⟩.
Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk

ACM Transactions on Algorithms, Association for Computing Machinery, 2018, 14 (3), pp.#38. ⟨10.1145/3196276⟩. ⟨lirmm-01919000⟩.
Bounds on the burning number
Stéphane Bessy, Anthony Bonato, Jeannette Janssen, Dieter Rautenbach, Elham Roshanbin

Discrete Applied Mathematics, Elsevier, 2018, 235, pp.16-22. ⟨10.1016/j.dam.2017.09.012⟩. ⟨lirmm-01713736⟩.
The $k$-strong induced arboricity of a graph
Maria Axenovich, Daniel Gonçalves, Jonathan Rollin, Torsten Ueckerdt

European Journal of Combinatorics, Elsevier, 2018, 67, pp.1-20. ⟨10.1016/j.ejc.2017.05.010⟩. ⟨lirmm-01888032⟩.
Polynomial expansion and sublinear separators
Louis Esperet, Jean-Florent Raymond

European Journal of Combinatorics, Elsevier, 2018, 69, pp.49-53. ⟨10.1016/j.ejc.2017.09.003⟩. ⟨hal-01525782⟩.

2017

Multigraphs without large bonds are wqo by contraction
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

Journal of Graph Theory, Wiley, 2017, ⟨10.1002/jgt.22229⟩. ⟨lirmm-01140407v2⟩. <10.1002/jgt.22229>
2-subcoloring is NP-complete for planar comparability graphs
Pascal Ochem

Information Processing Letters, Elsevier, 2017, 128, pp.46-48. ⟨10.1016/j.ipl.2017.08.004⟩. ⟨lirmm-01692394⟩.
Burning a graph is hard
Stéphane Bessy, Anthony Bonato, Jeannette Janssen, Dieter Rautenbach, Elham Roshanbin

Discrete Applied Mathematics, Elsevier, 2017, 232, pp.73-87. ⟨10.1016/j.dam.2017.07.016⟩. ⟨lirmm-01692784⟩.
The Geodetic Hull Number is Hard for Chordal Graphs
Stéphane Bessy, Mitre Dourado, Lucia Penso, Dieter Rautenbach

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.291-296. ⟨10.1016/j.endm.2017.10.050⟩. ⟨lirmm-01997425⟩.
Ruling out FPT algorithms for Weighted Coloring on forests
Julio Araujo, Julien Baste, Ignasi Sau

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.195-200. ⟨10.1016/j.endm.2017.10.034⟩. ⟨hal-01733595⟩.
Möbius Stanchion Systems
Lucas Isenmann, Timothée Pecatte

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.177-182. ⟨10.1016/j.endm.2017.10.031⟩. ⟨hal-01995308⟩.
On the difference between the Szeged and the Wiener index
Marthe Bonamy, Martin Knor, Borut Lužar, Alexandre Pinlou, Riste Škrekovski

Applied Mathematics and Computation, Elsevier, 2017, 312, pp.202-213. ⟨10.1016/j.amc.2017.05.047⟩. ⟨lirmm-01730264⟩.
Avoidability of Formulas with Two Variables
Pascal Ochem, Matthieu Rosenfeld

The Electronic Journal of Combinatorics, Open Journal Systems, 2017, 24 (4), pp.#P4.30. ⟨https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p30⟩. ⟨lirmm-01897592⟩.
Maximum Cuts in Edge-colored Graphs
Rubens Sucupira, Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton Souza

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.87 - 92. ⟨10.1016/j.endm.2017.10.016⟩. ⟨hal-01733581⟩.
Colouring diamond-free graphs
Konrad Dabrowski, François Dross, Daniël Paulusma

Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.410-431. ⟨10.1016/j.jcss.2017.06.005⟩. ⟨lirmm-01925569⟩.
A polynomial-time algorithm for Outerplanar Diameter Improvement
Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, Mathias Weller

Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.315 - 327. ⟨10.1016/j.jcss.2017.05.016⟩. ⟨hal-01592242⟩.
Parameterized Complexity Dichotomy for (r, ℓ)-Vertex Deletion
Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau

Theory of Computing Systems, Springer Verlag, 2017, 61 (3), pp.777-794. ⟨10.1007/s00224-016-9716-y⟩. ⟨lirmm-01630773⟩.
An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion
Mamadou Moustapha Kanté, Eun Jung Kim, O-Joung Kwon, Christophe Paul

Algorithmica, Springer Verlag, 2017, 79 (1), pp.66-95. ⟨10.1007/s00453-016-0230-z⟩. ⟨lirmm-01692676⟩.
Dushnik-Miller dimension of contact systems of d -dimensional boxes
Mathew Francis, Daniel Gonçalves

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 61, pp.467-473. ⟨10.1016/j.endm.2017.06.075⟩. ⟨lirmm-01693192⟩.
Parameterized complexity of the MINCCA problem on graphs of bounded decomposability
Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordechai Shalom

Theoretical Computer Science, Elsevier, 2017, 690, pp.91-103. ⟨10.1016/j.tcs.2017.06.013⟩. ⟨lirmm-01630777⟩.
Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang Conjecture
Stéphane Bessy, Jocelyn Thiebaut

Electronic Notes in Discrete Mathematics, Elsevier, 2017, 61, pp.115-121. ⟨10.1016/j.endm.2017.06.028⟩. ⟨lirmm-01713782⟩.
Extremal Values of the Chromatic Number for a Given Degree Sequence
Stéphane Bessy, Dieter Rautenbach

Graphs and Combinatorics, Springer Verlag, 2017, 33 (4), pp.789-799. ⟨10.1007/s00373-017-1814-3⟩. ⟨lirmm-01997424⟩.
Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
Nazanin Movarraei, Pascal Ochem

Information Processing Letters, Elsevier, 2017, 123, pp.42-46. ⟨10.1016/j.ipl.2017.02.009⟩. ⟨lirmm-02083721⟩.
Colorful paths for 3-chromatic graphs
Nicolas Bousquet, Stéphane Bessy

Discrete Mathematics, Elsevier, 2017, 340 (5), pp.1000-1007. ⟨10.1016/j.disc.2017.01.016⟩. ⟨hal-01592548⟩.
Editing to a planar graph of given degrees
Konrad Dabrowski, Petr A. Golovach, Pim Van 'T Hof, Daniël Paulusma, Dimitrios M. Thilikos

Journal of Computer and System Sciences, Elsevier, 2017, 85, pp.168-182. ⟨10.1016/j.jcss.2016.11.009⟩. ⟨hal-01632341⟩.
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau, Rémi Watrigant

Discrete Mathematics and Theoretical Computer Science, DMTCS, 2017, FCT '15, 19 (4), ⟨10.23638/DMTCS-19-4-3⟩. ⟨lirmm-01889400⟩. <10.23638/DMTCS-19-4-3>
Parameterized algorithms for min-max multiway cut and list digraph homomorphism
Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Journal of Computer and System Sciences, Elsevier, 2017, 86, pp.191-206. ⟨10.1016/j.jcss.2017.01.003⟩. ⟨lirmm-01487567⟩.
On the parameterized complexity of the Edge Monitoring problem
Julien Baste, Fairouz Beggas, Hamamache Kheddouci, Ignasi Sau

Information Processing Letters, Elsevier, 2017, 121, pp.39-44. ⟨10.1016/j.ipl.2017.01.008⟩. ⟨lirmm-01487565⟩.
Bounds on the exponential domination number
Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

Discrete Mathematics, Elsevier, 2017, 340 (3), pp.494-503. ⟨10.1016/j.disc.2016.08.024⟩. ⟨lirmm-01692753⟩.
Acyclic edge coloring through the Lovász Local Lemma
Dimitrios M. Thilikos, Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos

Theoretical Computer Science, Elsevier, 2017, 665, pp.40 - 50. ⟨10.1016/j.tcs.2016.12.011⟩. ⟨hal-01632338⟩.
On the complexity of computing the k-restricted edge-connectivity of a graph
Luis Pedro Montejano, Ignasi Sau

Theoretical Computer Science, Elsevier, 2017, 662, pp.31-39. ⟨10.1016/j.tcs.2016.12.006⟩. ⟨lirmm-01481786⟩.
A linear kernel for planar red–blue dominating set
Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos

Discrete Applied Mathematics, Elsevier, 2017, 217, pp.536-547. ⟨10.1016/j.dam.2016.09.045⟩. ⟨lirmm-01481785⟩.
Homomorphisms of 2-edge-colored triangle-free planar graphs
Pascal Ochem, Alexandre Pinlou, Sagnik Sen

Journal of Graph Theory, Wiley, 2017, 85 (1), pp.258-277. ⟨10.1002/jgt.22059⟩. ⟨lirmm-01376130⟩.
On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
Iyad Kanj, Dimitrios M. Thilikos, Ge Xia

Information and Computation, Elsevier, 2017, 257 (139-156), ⟨10.1016/j.ic.2017.11.002⟩. ⟨hal-01689398⟩. <10.1016/j.ic.2017.11.002>
The Parameterized Complexity of Graph Cyclability
Petr Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (1), pp.511 - 541. ⟨10.1137/141000014⟩. ⟨hal-01632332⟩.
Encoding toroidal triangulations
Vincent Despré, Daniel Gonçalves, Benjamin Lévêque

Discrete and Computational Geometry, Springer Verlag, 2017, 57 (57), pp.507-544. ⟨10.1007/s00454-016-9832-0⟩. ⟨hal-01488931⟩.
Recent techniques and results on the Erdős-Pósa property
Jean-Florent Raymond, Dimitrios M. Thilikos

Discrete Applied Mathematics, Elsevier, 2017, 231, pp.25-43. ⟨10.1016/j.dam.2016.12.025⟩. ⟨lirmm-01486771v2⟩.
Well-quasi-ordering $H$-contraction-free graphs
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

Discrete Applied Mathematics, Elsevier, 2017, In press. ⟨10.1016/j.dam.2017.02.018⟩. ⟨lirmm-01486775v2⟩. <10.1016/j.dam.2017.02.018>
The complexity of partitioning into disjoint cliques and a triangle-free graph
Marin Bougeret, Pascal Ochem

Discrete Applied Mathematics, Elsevier, 2017, 217, pp.438-445. ⟨10.1016/j.dam.2016.10.004⟩. ⟨lirmm-02078169⟩.
Low Polynomial Exclusion of Planar Graph Patterns
Jean-Florent Raymond, Dimitrios M. Thilikos

Journal of Graph Theory, Wiley, 2017, 84 (1), pp.26-44. ⟨10.1002/jgt.22009⟩. ⟨lirmm-01263767⟩.
List Coloring with a Bounded Palette
Marthe Bonamy, Ross J. Kang

Journal of Graph Theory, Wiley, 2017, 84 (1), pp.93-103. ⟨10.1002/jgt.22013⟩. ⟨lirmm-01264435⟩.
Packing and covering immersion-expansions of planar sub-cubic graphs
Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos

European Journal of Combinatorics, Elsevier, 2017, 65, pp.154-167. ⟨10.1016/j.ejc.2017.05.009⟩. ⟨lirmm-01610005v2⟩.
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
François Dross, Mickaël Montassier, Alexandre Pinlou

European Journal of Combinatorics, Elsevier, 2017, 66, pp.81-94. ⟨10.1016/j.ejc.2017.06.014⟩. ⟨lirmm-01430784⟩.
Minors in graphs of large θr-girth
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

European Journal of Combinatorics, Elsevier, 2017, 65, pp.106-121. ⟨10.1016/j.ejc.2017.04.011⟩. ⟨hal-01218519v2⟩.
Irrelevant vertices for the planar Disjoint Paths Problem
Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos

Journal of Combinatorial Theory, Series B, Elsevier, 2017, 122, pp.815-843. ⟨10.1016/j.jctb.2016.10.001⟩. ⟨hal-01632343⟩.
Antistrong digraphs
Jørgen Bang-Jensen, Stéphane Bessy, Bill Jackson, Matthias Kriesell

Journal of Combinatorial Theory, Series B, Elsevier, 2017, 122, pp.68-90. ⟨10.1016/j.jctb.2016.05.004⟩. ⟨lirmm-01348862⟩.
Computing a Clique Tree with the Algorithm Maximal Label Search
Anne Berry, Geneviève Simonet

Algorithms, MDPI, 2017, 10 (1), pp.#20. ⟨10.3390/a10010020⟩. ⟨lirmm-01693126⟩.

2016

(Meta) Kernelization
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos

Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (5), pp.#44. ⟨10.1145/2973749⟩. ⟨lirmm-01483628⟩.
Exponential Domination in Subcubic Graphs
Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (4), pp.#P4.42. ⟨lirmm-01997215⟩.
Orienting Triangulations
Boris Albar, Daniel Gonçalves, Kolja Knauer

Journal of Graph Theory, Wiley, 2016, 83 (4), pp.392-405. ⟨10.1002/jgt.22005⟩. ⟨hal-01457782⟩.
On the complexity of Wafer-to-Wafer Integration
Marin Bougeret, Vincent Boudet, Trivikram Dokka, Guillerme Duvillié, Rodolphe Giroudeau

Discrete Optimization, Elsevier, 2016, 22 (part B), pp.255-269. ⟨10.1016/j.disopt.2016.07.001⟩. ⟨lirmm-01378579⟩.
An edge variant of the Erdős–Pósa property
Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

Discrete Mathematics, Elsevier, 2016, 339 (8), pp.2027-2035. ⟨10.1016/j.disc.2016.03.004⟩. ⟨lirmm-01347430v2⟩.
Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou

Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, 17 (3), pp.131-146. ⟨lirmm-01347027v2⟩.
Parameterized certificate dispersal and its variants
Valentin Garnero, Mathias Weller

Theoretical Computer Science, Elsevier, 2016, 622, pp.66-78. ⟨10.1016/j.tcs.2016.02.001⟩. ⟨lirmm-01348417⟩.
Detecting minors in matroids through triangles
Boris Albar, Daniel Gonçalves, Jorge L. Ramírez Alfonsín

European Journal of Combinatorics, Elsevier, 2016, 53, pp.50-58. ⟨10.1016/j.ejc.2015.10.010⟩. ⟨lirmm-01263827⟩.
Approximating the sparsest $k$-subgraph in chordal graph
Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau

Theory of Computing Systems, Springer Verlag, 2016, 58 (1), pp.111-132. ⟨10.1007/s00224-014-9568-2⟩. ⟨lirmm-01383119⟩.
On interval representations of graphs
Aquiles Braga de Queiroz, Valentin Garnero, Pascal Ochem

Discrete Applied Mathematics, Elsevier, 2016, 202, pp.30-36. ⟨10.1016/j.dam.2015.08.022⟩. ⟨lirmm-01348411⟩.
Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique
Christophe Paul, Anthony Perez, Stéphan Thomassé

Journal of Computer and System Sciences, Elsevier, 2016, 82 (2), ⟨10.1016/j.jcss.2015.08.002⟩. ⟨hal-01367979⟩. <10.1016/j.jcss.2015.08.002>
Doubled patterns are 3-avoidable
Pascal Ochem

The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (1), pp.P1.19. ⟨http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p19/pdf⟩. ⟨lirmm-01375763⟩.
Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar

ACM Transactions on Algorithms, Association for Computing Machinery, 2016, 12 (2), pp.No. 21. ⟨10.1145/2797140⟩. ⟨lirmm-01288472⟩.
Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
Stanislav Jendrol', Mária Maceková, Mickaël Montassier, Roman Soták

Discrete Mathematics, Elsevier, 2016, 339 (2), pp.780 - 789. ⟨10.1016/j.disc.2015.10.016⟩. ⟨lirmm-01263824⟩.
Minimal disconnected cuts in planar graphs
Marcin Kamiński, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos

Networks, Wiley, 2016, 68 (4), pp.250-259. ⟨10.1002/net.21696⟩. ⟨lirmm-01483626⟩.
A short proof that shuffle squares are 7-avoidable
Guillaume Guégan, Pascal Ochem

RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2016, 50 (1), pp.101-103. ⟨10.1051/ita/2016007⟩. ⟨lirmm-01347424⟩.
3-path in graphs with bounded average degree
Stanislav Jendrol, Mária Maceková, Mickaël Montassier, Roman Soták

Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2016, 36 (2), pp.339-353. ⟨10.7151/dmgt.1859⟩. ⟨lirmm-01346642⟩.
Fractional Triangle Decompositions in Graphs with Large Minimum Degree
François Dross

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (1), pp.36-42. ⟨10.1137/15M1014310⟩. ⟨lirmm-01336680⟩.
Islands in graphs on surfaces
Louis Esperet, Pascal Ochem

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (1), pp.206-219. ⟨10.1137/140957883⟩. ⟨hal-01119804⟩.
Coloring non-crossing strings
Louis Esperet, Daniel Gonçalves, Arnaud Labourel

The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (4), pp.4.4. ⟨http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p4⟩. ⟨hal-01480244⟩.
Scattered packings of cycles
Aistis Atminas, Marcin Kamiński, Jean-Florent Raymond

Theoretical Computer Science, Elsevier, 2016, 647, pp.33 - 42. ⟨10.1016/j.tcs.2016.07.021⟩. ⟨hal-01401905⟩.
On the consistency of orthology relationships
Mark Jones, Christophe Paul, Celine Scornavacca

BMC Bioinformatics, BioMed Central, 2016, 17 (S14), ⟨10.1186/s12859-016-1267-3⟩. ⟨lirmm-01481206⟩. <10.1186/s12859-016-1267-3>
A lower bound on the order of the largest induced forest in planar graphs with high girth
François Dross, Mickaël Montassier, Alexandre Pinlou

Discrete Applied Mathematics, Elsevier, 2016, 214, pp.99-107. ⟨lirmm-01375448⟩.
Contraction Obstructions for Connected Graph Searching
Best Micah J, Arvind Gupta, Dimitrios M. Thilikos, Dimitris Zoros

Discrete Applied Mathematics, Elsevier, 2016, 209, pp.27-47. ⟨10.1016/j.dam.2015.07.036⟩. ⟨lirmm-01349860⟩.

2015

Independent Domination in Cubic Graphs
Paul Dorbec, Michael A. Henning, Mickaël Montassier, Justin Southey

Journal of Graph Theory, Wiley, 2015, 80 (4), pp.329-349. ⟨10.1002/jgt.21855⟩. ⟨lirmm-01263782⟩.
Planar Disjoint-Paths Completion
Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos

Algorithmica, Springer Verlag, 2015, 76 (2), pp.401-425. ⟨http://link.springer.com/article/10.1007/s00453-015-0046-2⟩. ⟨10.1007/s00453-015-0046-2⟩. ⟨lirmm-01370272⟩.
Strong edge coloring sparse graphs
Julien Bensmail, Marthe Bonamy, Hervé Hocquard

Electronic Notes in Discrete Mathematics, Elsevier, 2015, The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, 49, pp.773-778. ⟨10.1016/j.endm.2015.06.104⟩. ⟨lirmm-01264420⟩.
Complexity dichotomy for oriented homomorphism of planar graphs with large girth
Guillaume Guégan, Pascal Ochem

Theoretical Computer Science, Elsevier, 2015, 596, pp.142-148. ⟨10.1016/j.tcs.2015.06.041⟩. ⟨lirmm-01263869⟩.
Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles
Jørgen Bang-Jensen, Stéphane Bessy

Journal of Graph Theory, Wiley, 2015, 79 (4), pp.249-266. ⟨10.1002/jgt.21830⟩. ⟨lirmm-01282883⟩.
Characterization of some binary words with few squares
Golnaz Badkobeh, Pascal Ochem

Theoretical Computer Science, Elsevier, 2015, 588, pp.73-80. ⟨10.1016/j.tcs.2015.03.044⟩. ⟨lirmm-01263844⟩.
The Maximum Clique Problem in Multiple Interval Graphs
Mathew C. Francis, Daniel Gonçalves, Pascal Ochem

Algorithmica, Springer Verlag, 2015, 71 (4), pp.812-836. ⟨10.1007/s00453-013-9828-6⟩. ⟨lirmm-01263898⟩.
The role of planarity in connectivity problems parameterized by treewidth
Julien Baste, Ignasi Sau

Theoretical Computer Science, Elsevier, 2015, 570, pp.1-14. ⟨10.1016/j.tcs.2014.12.010⟩. ⟨lirmm-01272664⟩.
Asteroidal quadruples in non rooted path graphs
Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato

Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2015, 35 (4), pp.603-614. ⟨10.7151/dmgt.1821⟩. ⟨lirmm-01348863⟩.
Planar graphs with $\Delta\geq 8$ are ($\Delta+1$)-edge-choosable
Marthe Bonamy

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (3), pp.1735-1763. ⟨10.1137/130927449⟩. ⟨lirmm-01264429⟩.
Hadwiger Number of Graphs with Small Chordality
Petr A. Golovach, Pinar Heggernes, Pim Van 'T Hof, Christophe Paul

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (3), pp.1427-1451. ⟨10.1137/140975279⟩. ⟨hal-01263856⟩.
Identifying codes in hereditary classes of graphs and VC-dimension
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, Stéphan Thomassé

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (4), pp.2047-2064. ⟨http://epubs.siam.org/doi/abs/10.1137/14097879X⟩. ⟨10.1137/14097879X⟩. ⟨hal-01038012v2⟩.
Near-colorings: non-colorable graphs and NP-completeness
Mickaël Montassier, Pascal Ochem

The Electronic Journal of Combinatorics, Open Journal Systems, 2015, 22 (1), pp.#P1.57. ⟨lirmm-01263770⟩.
Explicit Linear Kernels via Dynamic Programming
Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (4), pp.1864-1894. ⟨10.1137/140968975⟩. ⟨lirmm-01263857⟩.
Design of fault-tolerant on-board networks with variable switch sizes
Olivier Delmas, Frédéric Havet, Mickaël Montassier, Stéphane Pérennes

Theoretical Computer Science, Elsevier, 2015, 562, pp.75-89. ⟨10.1016/j.tcs.2014.09.034⟩. ⟨hal-01111370⟩.
Two floor building needing eight colors
Stéphane Bessy, Daniel Gonçalves, Jean-Sébastien Sereni

Journal of Graph Algorithms and Applications (JGAA), Brown University, 2015, 19 (1), pp.1--9. ⟨http://dx.doi.org/10.7155/jgaa.00344⟩. ⟨hal-00996709v2⟩.
Excluding cycles with a fixed number of chords
Pierre Aboulker, Nicolas Bousquet

Discrete Applied Mathematics, Elsevier, 2015, 180, pp.11-24. ⟨10.1016/j.dam.2014.08.006⟩. ⟨lirmm-01350552⟩.
Forbidding Kuratowski Graphs as Immersions
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos

Journal of Graph Theory, Wiley, 2015, 78 (1), pp.43-60. ⟨10.1002/jgt.21790⟩. ⟨lirmm-00904533⟩.
A single-exponential FPT algorithm for the $K_4$-minor cover problem
Kim Eun Jung, Christophe Paul, Geevarghese Philip

Journal of Computer and System Sciences, Elsevier, 2015, 81 (1), pp.186-207. ⟨hal-01178194⟩.
The Erdős–Hajnal conjecture for paths and antipaths
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé

Journal of Combinatorial Theory, Series B, Elsevier, 2015, 113, pp.261-264. ⟨10.1016/j.jctb.2015.01.001⟩. ⟨hal-01134469⟩.

2014

On the bend-number of planar and outerplanar graphs
Daniel Heldt, Kolja Knauer, Torsten Ueckerdt

Discrete Applied Mathematics, Elsevier, 2014, 179, pp.109-119. ⟨10.1016/j.dam.2014.07.015⟩. ⟨lirmm-01414962⟩.
Organizing the atoms of the clique separator decomposition into an atom tree
Anne Berry, Romain Pogorelcnik, Geneviève Simonet

Discrete Applied Mathematics, Elsevier, 2014, 177, pp.1-13. ⟨10.1016/j.dam.2014.05.030⟩. ⟨hal-01375915⟩.
2-Distance Coloring of Sparse Graphs
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou

Journal of Graph Theory, Wiley, 2014, 77 (3), pp.190-218. ⟨10.1002/jgt.21782⟩. ⟨lirmm-01233451⟩.
Binary patterns in binary cube-free words: Avoidability and growth
Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur

RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (4), pp.369-389. ⟨10.1051/ita/2014015⟩. ⟨lirmm-01263848⟩.
List coloring the square of sparse graphs with large degree
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou

European Journal of Combinatorics, Elsevier, 2014, 41, pp.128-137. ⟨10.1016/j.ejc.2014.03.006⟩. ⟨lirmm-01233445⟩.
On the number of prime factors of an odd perfect number
Pascal Ochem, Michael Rao

Mathematics of Computation, American Mathematical Society, 2014, 83 (289), pp.2435-2439. ⟨10.1090/S0025-5718-2013-02776-7⟩. ⟨lirmm-01263897⟩.
Another remark on the radical of an ODD perfect number
Pascal Ochem, Michaël Rao

The Fibonacci Quarterly, Dalhousie University, 2014, 52 (3), ⟨315-317⟩. ⟨lirmm-01349855⟩. <315-317>
Brooks’ theorem on powers of graphs
Marthe Bonamy, Nicolas Bousquet

Discrete Mathematics, Elsevier, 2014, 325, pp.12-16. ⟨10.1016/j.disc.2014.01.024⟩. ⟨lirmm-01264422⟩.
Computation with No Memory, and Rearrangeable Multicast Networks
Emeric Gioan, Serge Burckel, Emmanuel Thomé

Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.121-142. ⟨lirmm-00959964⟩.
Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs
Pascal Ochem, Alexandre Pinlou

Graphs and Combinatorics, Springer Verlag, 2014, 30 (2), pp.439-453. ⟨10.1007/s00373-013-1283-2⟩. ⟨lirmm-00780910⟩.
Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments
Jørgen Bang-Jensen, Stéphane Bessy, Stéphan Thomassé

Journal of Graph Theory, Wiley, 2014, 75 (3), pp.284-302. ⟨10.1002/jgt.21740⟩. ⟨lirmm-01282882⟩.
(Arc-)disjoint flows in networks
Jørgen Bang-Jensen, Stéphane Bessy

Theoretical Computer Science, Elsevier, 2014, 526, pp.28-40. ⟨10.1016/j.tcs.2014.01.011⟩. ⟨lirmm-01282881⟩.
Outerplanar obstructions for matroid pathwidth
Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

Discrete Mathematics, Elsevier, 2014, 315, pp.95-101. ⟨10.1016/j.disc.2013.10.007⟩. ⟨lirmm-01225581⟩.
Graphs with maximum degree Δ≥17 and maximum average degree less than 3 are list 2-distance (Δ+2)-colorable
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou

Discrete Mathematics, Elsevier, 2014, 317, pp.19-32. ⟨10.1016/j.disc.2013.10.022⟩. ⟨lirmm-01233453⟩.
More on square-free words obtained from prefixes by permutations
Pascal Ochem

Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, Russian-Finnish Symposium in Discrete Mathematics, 132 (1), pp.109-112. ⟨10.3233/FI-2014-1035⟩. ⟨lirmm-01375793⟩.
Strong chromatic index of planar graphs with large girth
Gerard Jennhwa Chang, Mickaël Montassier, Arnaud Pêcher, André Raspaud

Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2014, 34 (4), pp.723-733. ⟨10.7151/dmgt.1763⟩. ⟨hal-00920932⟩.
Practical and Efficient Split Decomposition via Graph-Labelled Trees
Emeric Gioan, Christophe Paul, Marc Tedder, Derek Corneil

Algorithmica, Springer Verlag, 2014, 69 (4), pp.789-843. ⟨10.1007/s00453-013-9752-9⟩. ⟨lirmm-00805193⟩.
Contracting Graphs to Paths and Trees
Pinar Heggernes, Pim Van ’t Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul

Algorithmica, Springer Verlag, 2014, 68 (1), pp.109-132. ⟨10.1007/s00453-012-9670-2⟩. ⟨lirmm-01076841⟩.
Practical and Efficient Circle Graph Recognition
Emeric Gioan, Christophe Paul, Marc Tedder, Derek Corneil

Algorithmica, Springer Verlag, 2014, 69 (4), pp.759-788. ⟨10.1007/s00453-013-9745-8⟩. ⟨lirmm-00805194⟩.
Hitting and harvesting pumpkins
Gwénaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé

Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (3), pp.1363-1390. ⟨10.1137/120883736⟩. ⟨hal-01178192⟩.
Application of entropy compression in pattern avoidance
Pascal Ochem, Alexandre Pinlou

The Electronic Journal of Combinatorics, Open Journal Systems, 2014, 21 (2), pp.1-12. ⟨http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7⟩. ⟨lirmm-01233448⟩.
Parameterized domination in circle graphs
Christophe Paul, Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Ignasi Sau, Stéphan Thomassé

Theory of Computing Systems, Springer Verlag, 2014, 54 (1), pp.45-72. ⟨10.1007/s00224-013-9478-8⟩. ⟨hal-01178188⟩.
Dynamic Programming for Graphs on Surfaces
Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos

ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 10 (2), pp.Article No. 8. ⟨10.1145/2556952⟩. ⟨lirmm-01083690⟩.
Contracting chordal graphs and bipartite graphs to paths and trees
Pinar Heggernes, Pim Van ’t Hof, Benjamin Lévêque, Christophe Paul

Discrete Applied Mathematics, Elsevier, 2014, LAGOS’11: Sixth Latin American Algorithms, Graphs, and Optimization Symposium, Bariloche, Argentina, 164, pp.444-449. ⟨10.1016/j.dam.2013.02.025⟩. ⟨lirmm-01266352⟩.
Square roots of minor closed graph classes
Nestor Nestoridis, Dimitrios M. Thilikos

Discrete Applied Mathematics, Elsevier, 2014, 168, pp.34 - 39. ⟨10.1016/j.dam.2013.05.026⟩. ⟨hal-01083980v2⟩.
Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations
Daniel Gonçalves, Benjamin Lévêque

Discrete and Computational Geometry, Springer Verlag, 2014, 51 (1), pp.67-131. ⟨10.1007/s00454-013-9552-7⟩. ⟨lirmm-01263819⟩.
Clique versus Independent Set
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé

European Journal of Combinatorics, Elsevier, 2014, 40, pp.73-92. ⟨http://www.sciencedirect.com/science/article/pii/S0195669814000249⟩. ⟨10.1016/j.ejc.2014.02.003⟩. ⟨hal-00958647⟩.
Lift-contractions
Petr A. Golovach, Daniël Paulusma, Marcin Kamiski, Dimitrios M. Thilikos

European Journal of Combinatorics, Elsevier, 2014, 35, pp.286 - 296. ⟨10.1016/j.ejc.2013.06.026⟩. ⟨hal-01083984⟩.

Communications internationales

2019

New Polynomial-Time Algorithm around the Scaffolding Problem
Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller

AlCoB: Algorithms for Computational Biology, May 2019, Berkeley, United States. ⟨lirmm-02047701⟩. <http://alcob2019.irdta.eu>
Connected tree-width and connected cops and robber game
Christophe Paul

CAALM: Complexity, Algorithms, Automata and Logic Meet, Jan 2019, Chennai, India. ⟨lirmm-02079017⟩. <https://www.cmi.ac.in/~sri/CAALM2019/>
Every Collinear Set in a Planar Graph Is Free
Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, Günter Rote

Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), Jan 2019, San Diego, United States. pp.1521-1538. ⟨lirmm-02046476⟩.

2018

A polynomial Turing kernel to compute the cut-width of semi-complete digraph
Christophe Paul

FILOFOCS: French-Israeli Workshop on Foundations of Computer Science, Oct 2018, Paris, France. ⟨lirmm-02078882⟩. <https://www.irif.fr/~adiro/filofocs/filofocs2018/index.html>
Discrete Morse theory for the collapsibility of supremum sections
Balthazar Bauer, Lucas Isenmann

ICGT: International Colloquium on Graph Theory and combinatorics, Jul 2018, Lyon, France. ⟨hal-01867246⟩. <https://projet.liris.cnrs.fr/~icgt2018/>
Partial complementation of graphs
Fedor Fomin, Petr Golovach, Torstein Strømme, Dimitrios M. Thilikos

SWAT: Scandinavian Workshops on Algorithm Theory, Jun 2018, Malmö, Sweden. pp.21:1--21:13, ⟨10.4230/LIPIcs.SWAT.2018.21⟩. ⟨lirmm-01890534⟩.
Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma
Ioannis Giotis, Lefteris Kirousis, John Livieratos, Kostas Psaromiligkos, Dimitrios M. Thilikos

GASCom: Random and Exhaustive Generation of Combinatorial Structures, Jun 2018, Athens, Greece. pp.148-155. ⟨lirmm-01890510⟩.
Temporal matching in link stream: kernel and approximation
Julien Baste, Binh-Minh Bui-Xuan

16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018), Jun 2018, Paris, France. ⟨hal-02075831⟩.
Planar Graphs as L-intersection or L-contact graphs
Daniel Gonçalves, Lucas Isenmann, Claire Pennarun

SODA: Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. ⟨10.1137/1.9781611975031.12⟩. ⟨lirmm-01738150⟩. <10.1137/1.9781611975031.12>

2017

On Some Interesting Ternary Formulas
Pascal Ochem, Matthieu Rosenfeld

WORDS, Sep 2017, Montreal, Canada. pp.30-35, ⟨10.1007/978-3-319-66396-8_4⟩. ⟨lirmm-02078252⟩.
Contraction-Bidimensionality of Geometric Intersection Graphs
Julien Baste, Dimitrios M. Thilikos

IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. pp.5:1--5:13, ⟨10.4230/LIPIcs.IPEC.2017.5⟩. ⟨lirmm-01890527⟩.
Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter
Julien Baste, Didem Gözüpek, Ignasi Sau, Mordechai Shalom, Dimitrios M. Thilikos

IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienna, Austria. pp.3:1--3:12, ⟨10.4230/LIPIcs.IPEC.2017.3⟩. ⟨hal-01733767⟩.
Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienna, Austria. pp.4:1--4:12, ⟨10.4230/LIPIcs.IPEC.2017.4⟩. ⟨hal-01733845⟩.
Triangle packing in (sparse) tournaments: approximation and kernelization *
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut

ESA: European Symposium on Algorithms, Sep 2017, Vienne, Austria. pp.1-23, ⟨10.4230/LIPIcs.ESA.2017⟩. ⟨lirmm-01550313⟩.
How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Marin Bougeret, Ignasi Sau

IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. pp.10:1--10:13, ⟨10.4230/LIPIcs.IPEC.2017.10⟩. ⟨lirmm-01730228⟩.
Structured Connectivity Augmentation
Fedor Fomin, Petr Golovach, Dimitrios M. Thilikos

MFCS: Mathematical Foundations of Computer Science, Aug 2017, Aalborg, Denmark. ⟨10.4230/LIPIcs.MFCS.2017.29⟩. ⟨lirmm-01890542⟩. <10.4230/LIPIcs.MFCS.2017.29>
Integer vectors and combinatorial properties of affine dependencies of ±1 vectors over the reals
Emeric Gioan, Ilda Da Silva

Symmetry in Finite and Infinite Structures, Jul 2017, Lisbonne, Portugal. ⟨lirmm-01729737⟩.
Complexity Dichotomies for the Minimum $F$-Overlay Problem
Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant

IWOCA: International Workshop on Combinatorial Algorithms, Jul 2017, Newcastle, Australia. pp.12. ⟨hal-01571229⟩.
Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk

ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2017, Warsaw, Poland. pp.70:1--70:13, ⟨10.4230/LIPIcs.ICALP.2017.70⟩. ⟨lirmm-02021567⟩.
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2017, Varsovie, Poland. pp.1-15, ⟨10.4230/LIPIcs.ICALP.2017.57⟩. ⟨lirmm-01610076⟩.
Uniquely Restricted Matchings and Edge Colorings
Julien Baste, Dieter Rautenbach, Ignasi Sau

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. pp.100-112, ⟨10.1007/978-3-319-68705-6_8⟩. ⟨hal-01734132⟩.
On the Number of Labeled Graphs of Bounded Treewidth
Julien Baste, Marc Noy, Ignasi Sau

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. pp.88-99, ⟨10.1007/978-3-319-68705-6_7⟩. ⟨hal-01734085⟩.
Dushnik-Miller dimension of TD-Delaunay complexes
Daniel Gonçalves, Lucas Isenmann

EuroCG: European Workshop on Computational Geometry, Apr 2017, Malmo, Sweden. ⟨lirmm-01888045⟩.

2016

On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs
Sancrey Rodrigues Alves, Konrad Kazimierz Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton dos Santos Souza

COCOA: Conference on Combinatorial Optimization and Applications, Dec 2016, Hong Kong, China. pp.423-437, ⟨10.1007/978-3-319-48749-6_31⟩. ⟨lirmm-01481787⟩.
Partitioning sparse graphs into an independent set and a forest of bounded degree
François Dross, Mickaël Montassier, Alexandre Pinlou

BGW: Bordeaux Graph Workshop, Nov 2016, Bordeaux, France. ⟨lirmm-01430813⟩. <http://bgw.labri.fr/2016/>
On a conjecture on k-Thue sequences
Borut Lužar, Martina Mockovčiaková, Pascal Ochem, Alexandre Pinlou, Roman Soták

BGW: Bordeaux Graph Workshop, Nov 2016, Bordeaux, France. ⟨lirmm-01730302⟩. <http://bgw.labri.fr/2016/>
Vertex-partitions of graphs
Mickaël Montassier

ICGCA: International Conference on Graph theory, Combinatorics and their Applications, Oct 2016, Jinhua, China. ⟨lirmm-01430816⟩.
Cutwidth: obstructions and algorithmic aspects
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

IPEC: International symposium on Parameterized and Exact Computation, Aug 2016, Aarhus, Denmark. pp.15:1--15:13, ⟨10.4230/LIPIcs.IPEC.2016.15⟩. ⟨lirmm-01370305⟩.
FPT Algorithms for Plane Completion Problems
Dimitris Chatzidimitriou, Archontia Giannopoulou, Spyridon Maniatis, Clément Requilé, Dimitrios M. Thilikos, Dimitris Zoros

MFCS: Mathematical Foundations of Computer Science, Aug 2016, Kraków, Poland. pp.26:1-26:13, ⟨10.4230/LIPIcs.MFCS.2016.26⟩. ⟨lirmm-01370324⟩.
Avoidability of Formulas with Two Variables
Pascal Ochem, Matthieu Rosenfeld

DLT: Developments in Language Theory, Laboratoire de combinatoire et d'informatique mathématique (LaCIM), Université du Québec à Montréal, Jul 2016, Montréal, Canada. pp.344-354, ⟨10.1007/978-3-662-53132-7_28⟩. ⟨lirmm-01375829⟩.
Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees
Julien Baste, Christophe Paul, Ignasi Sau, Celine Scornavacca

AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. pp.53-64, ⟨10.1007/978-3-319-41168-2_5⟩. ⟨lirmm-01481368⟩.
Packing and Covering Immersion Models of Planar subcubic Graphs
Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.74-84, ⟨10.1007/978-3-662-53536-3_7⟩. ⟨lirmm-01370310v2⟩.
Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability
Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordeshai Shalom

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.195-206, ⟨10.1007/978-3-662-53536-3_17⟩. ⟨lirmm-01481360⟩.
On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges)
Emeric Gioan

Graph Polynomials: Towards a Comparative Theory, Jun 2016, Dagstuhl seminar, Germany. ⟨lirmm-01370263⟩.
Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau

ISCO: International Symposium on Combinatorial Optimization, May 2016, Vietri sul Mare, Italy. pp.148-159, ⟨10.1007/978-3-319-45587-7_13⟩. ⟨lirmm-01383110⟩.
Colouring Diamond-free Graphs
Konrad K. Dabrowski, François Dross, Daniël Paulusma

SWAT: Scandinavian Workshops on Algorithm Theory, 2016, Reykjavik, Iceland. pp.16:1--16:14, ⟨10.4230/LIPIcs.SWAT.2016.16⟩. ⟨lirmm-01481433⟩.

2015

An FPT 2-Approximation for Tree-cut Decomposition
Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.35-46, ⟨10.1007/978-3-319-28684-6_4⟩. ⟨lirmm-01264015⟩.
An $O(log OPT)$-Approximation for Covering/Packing Minor Models of $θ _r$
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.122-132, ⟨10.1007/978-3-319-28684-6_11⟩. ⟨hal-01218496⟩.
On Independent Set on B1-EPG Graphs
Marin Bougeret, Stéphane Bessy, Daniel Gonçalves, Christophe Paul

WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.158-169, ⟨10.1007/978-3-319-28684-6_14⟩. ⟨lirmm-01264022⟩.
Variants of Plane Diameter Completion
Clément Requilé, Dimitrios M. Thilikos, Petr A. Golovach

IPEC: International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.30-42, ⟨10.4230/LIPIcs.IPEC.2015.30⟩. ⟨lirmm-01225566⟩.
An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion
Christophe Paul, Eun Jung Kim, Mamadou Moustapha Kanté, O-Joung Kwon

IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.139-150, ⟨10.4230/LIPIcs.IPEC.2015.138⟩. ⟨lirmm-01264011⟩.
Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.78-89, ⟨10.4230/LIPIcs.IPEC.2015.78⟩. ⟨lirmm-01263999⟩.
Bidimensionality and Parameterized Algorithms
Dimitrios M. Thilikos

IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.1-16, ⟨10.4230/LIPIcs.IPEC.2015.1⟩. ⟨lirmm-01370293⟩.
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
François Dross, Mickaël Montassier, Alexandre Pinlou

EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Aug 2015, Bergen, Norway. pp.269-275, ⟨10.1016/j.endm.2015.06.037⟩. ⟨lirmm-01233461⟩.
Induced minors and well-quasi-ordering
Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck

EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Aug 2015, Bergen, Norway. pp.197-201, ⟨10.1016/j.endm.2015.06.029⟩. ⟨lirmm-01349277⟩.
Minimal Disconnected Cuts in Planar Graphs
Marcin Kaminski, Daniël Paulusma, Stewart Anthony, Dimitrios M. Thilikos

FCT: Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. pp.243-254, ⟨10.1007/978-3-319-22177-9_19⟩. ⟨lirmm-01225549⟩.
Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau, Rémi Watrigant

FCT: Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. pp.189-201, ⟨10.1007/978-3-319-22177-9_15⟩. ⟨lirmm-01250997⟩.
A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
Nathann Cohen, Daniel Gonçalves, Kim Eun Jung, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, Mathias Weller

CSR: Computer Science in Russia, Jul 2015, Listvyanka, Russia. pp.123-142, ⟨10.1007/978-3-319-20297-6_9⟩. ⟨hal-01178222⟩.
Editing to a Planar Graph of Given Degrees
Konrad K. Dabrowski, Petr A. Golovach, Pim Van'T Hof, Daniël Paulusma, Dimitrios M. Thilikos

CSR: Computer Science in Russia, Jul 2015, Listvyanka, Russia. pp.143-156, ⟨10.1007/978-3-319-20297-6_10⟩. ⟨lirmm-01225602⟩.
A survey on the active bijection in graphs, hyperplane arrangements and oriented matroids
Emeric Gioan

Workshop on the Tutte polynomial, Jul 2015, London, United Kingdom. ⟨lirmm-01265667⟩. <https://tutte2015.ma.rhul.ac.uk>
Algorithms and Combinatorics on the Erdős–Pósa property
Dimitrios M. Thilikos

AGTAC: Algorithmic Graph Theory on the Adriatic Coast, Jun 2015, Koper, Slovenia. ⟨lirmm-01483655⟩. <https://conferences.matheo.si/event/6/page/12>
An alternative proof for the constructive Asymmetric Lovász Local Lemma
Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2015, İstanbul, Turkey. ⟨lirmm-01370328⟩. <http://ctw2015.eng.marmara.edu.tr>
A Fixed Parameter Algorithm for Plane Subgraph Completion
Dimitris Chatzidimitriou, Archontia C. Giannopoulou, Clément Requilé, Dimitrios M. Thilikos, Dimitris Zoros

CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2015, Istanbul, Turkey. ⟨lirmm-01370331⟩. <http://ctw2015.eng.marmara.edu.tr>
Orienting triangulations
Boris Albar, Daniel Gonçalves, Kolja Knauer

EuroCG: European Workshop on Computational Geometry, Mar 2015, Ljubljana, Slovenia. ⟨lirmm-01264309⟩. <http://eurocg15.fri.uni-lj.si>
On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring
Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

ANALCO: Analytic Algorithmics and Combinatorics, Jan 2015, San Diego, California, United States. ⟨10.1137/1.9781611973761.2⟩. ⟨lirmm-01225505⟩. <10.1137/1.9781611973761.2>
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
Konrad K. Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma

IWOCA: International Workshop on Combinatorial Algorithms, 2015, Verona, Italy. pp.100-111, ⟨10.1007/978-3-319-29516-9_9⟩. ⟨lirmm-01481412⟩.
Introduction to parameterized complexity and some algorithmic consequences of the graph minor theory
Christophe Paul

Workshop on Graph Theory and its Applications, 2015, Istanbul, Turkey. ⟨lirmm-02078876⟩.

2014

The role of planarity in connectivity problems parameterized by treewidth
Julien Baste, Ignasi Sau

IPEC: International symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.63-74, ⟨10.1007/978-3-319-13524-3_6⟩. ⟨lirmm-01481432⟩.
A 14k-Kernel for Planar Feedback Vertex Set via Region Decomposition
Marthe Bonamy, Lukasz Kowalik

IPEC: International symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.97-109, ⟨10.1007/978-3-319-13524-3_9⟩. ⟨lirmm-01264417⟩.
The Parameterized Complexity of Graph Cyclability
Petr A. Golovach, Marcin Kamiski, Spyridon Maniatis, Dimitrios M. Thilikos

ESA: European Symposium on Algorithms, Sep 2014, Wrocław, Poland. pp.492-504, ⟨10.1007/978-3-662-44777-2_41⟩. ⟨hal-01083993⟩.
Intersection Graphs of L-Shapes and Segments in the Plane
Stefan Felsner, Kolja Knauer, George B. Mertzios, Torsten Ueckerdt

MFCS: Mathematical Foundations of Computer Science, Aug 2014, Budapest, Hungary. pp.299-310, ⟨10.1007/978-3-662-44465-8_26⟩. ⟨lirmm-01414991⟩.
Quantifying trust dynamics in signed graphs, the S-Cores approach
Christos Giatsidis, Bogdan Cautis, Silviu Maniu, Michalis Vazirgiannis, Dimitrios M. Thilikos

SDM: SIAM Data Mining, Aug 2014, Philadelphia, United States. pp.668-676, ⟨10.1137/1.9781611973440.77⟩. ⟨lirmm-01083529⟩.
CORECLUSTER: A Degeneracy Based Graph Clustering Framework
Christos Giatsidis, Fragkiskos Malliaros, Dimitrios M. Thilikos, Michalis Vazirgiannis

IAAA: Innovative Applications of Artificial Intelligence, Jul 2014, Quebec City, Canada. ⟨lirmm-01083536⟩.
Entropy compression method applied to graph colorings
Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01233456⟩.
Recognition of dynamic circle graphs
Christophe Crespelle, Emeric Gioan, Christophe Paul

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨hal-01178215⟩. <http://oc.inpg.fr/conf/icgt2014/>
Contraction Obstructions for Connected Graph Searching
Best Micah J, Arvind Gupta, Dimitrios M. Thilikos, Dimitris Zoros

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01083704⟩.
Geometric Extensions of Cutwidth in any Dimension
Menelaos Karavelas, Dimitris Zoros, Spyridon Maniatis, Dimitrios M. Thilikos

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01083698⟩.
Covering and packing pumpkin models
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01083652⟩. <http://oc.inpg.fr/conf/icgt2014/>
Structure of W_4 -immersion free graphs
Rémy Belmonte, Archontia C. Giannopoulou, Daniel Lokshtanov, Dimitrios M. Thilikos

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨hal-01084005⟩.
Detecting minors in matroids throughout triangles
Boris Albar, Daniel Gonçalves, Jorge Ramírez Alfonsín

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01264288⟩. <http://oc.inpg.fr/conf/icgt2014/>
An edge variant of the Erdős-Pósa property
Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-00904544⟩.
Hadwiger Number of Graphs with Small Chordality
Petr A. Golovach, Pinar Heggernes, Pim Van 'T Hof, Christophe Paul

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2014, Nouan-le-Fuzelier, France. pp.201-213, ⟨10.1007/978-3-319-12340-0_17⟩. ⟨hal-01178217⟩.
Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
Steven Chaplick, Paul Dorbec, Jan Kratochvil, Mickaël Montassier, Juraj Stacho

WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2014, Nouan-le-fuzelier, France. pp.139-151, ⟨10.1007/978-3-319-12340-0_12⟩. ⟨lirmm-01264271⟩.
Explicit linear kernels via dynamic programming
Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. pp.312-324, ⟨10.4230/LIPIcs.STACS.2014.312⟩. ⟨hal-01084007⟩.
Bidimensionality of Geometric Intersection Graphs
Alexander Grigoriev, Athanassios Koutsonas, Dimitrios M. Thilikos

SOFSEM: Theory and Practice of Computer Science, Jan 2014, Špindlerův Mlýn, Czech Republic. pp.293-305, ⟨10.1007/978-3-319-04298-5_26⟩. ⟨lirmm-00904537⟩.
Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
Marin Bougeret, Nicolas Bousquet, Rodolphe Giroudeau, Rémi Watrigant

SOFSEM: Theory and Practice of Computer Science, Jan 2014, Nový Smokovec, Slovakia. pp.150-161, ⟨10.1007/978-3-319-04298-5_14⟩. ⟨lirmm-01251025⟩.
Making Octants Colorful and Related Covering Decomposition Problems
Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt

SODA: Symposium on Discrete Algorithms, Jan 2014, Portland, United States. pp.1424-1432, ⟨10.1137/1.9781611973402.105⟩. ⟨lirmm-01414977⟩.
Entropy compression method and graph coloring problems
Mickaël Montassier

C&C: Cycles and Colourings, 2014, Novy Smokovec, Slovakia. ⟨lirmm-01264376⟩.

Mots-clés

Algorithmique de Graphes, Théorie des Graphes, Combinatoire

Dernière mise à jour le 07/01/2019

Département : Informatique

Responsable : Mickael MONTASSIER

Site de l'équipe : http://www.lirmm.fr/algco

Fiche-équipe ALGCO

Télécharger la fiche-équipe ALGCO du rapport d'activité 2008-2013 :

Fiche-équipe ALGCO 2013