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

Non permanents

Publications depuis 2013 - Evaluation 2019

Articles de revues internationales

2018

  1. 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.
  2. 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.1-31.
  3. Structure and Enumeration of $K4$-minor-free links and link diagrams
    Juanjo Rué, Dimitrios M. Thilikos, Vasiliki Velonade
    Electronic Notes in Discrete Mathematics, Elsevier, 2018, 68, pp.119-124.
  4. On triangles in $Kr$-minor free graphs
    Boris Albar, Daniel Gonçalves
    Journal of Graph Theory, Wiley, 2018, 88 (1), pp.154-173.
  5. 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>
  6. Degenerate matchings and edge colorings
    Julien Baste, Dieter Rautenbach
    Discrete Applied Mathematics, Elsevier, 2018, 239, pp.38-44.
  7. 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.
  8. 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.
  9. Cutwidth: Obstructions and Algorithmic Aspects
    Archontia Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios Thilikos, Marcin Wrochna
    Algorithmica, Springer Verlag, 2018. <10.1007/s00453-018-0424-7>
  10. 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.
  11. 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.
  12. Hitting minors, subdivisions, and immersions in tournaments
    Jean-Florent Raymond
    Discrete Mathematics and Theoretical Computer Science, DMTCS, 2018, 20 (1), pp.4212.
  13. 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.
  14. Polynomial expansion and sublinear separators
    Louis Esperet, Jean-Florent Raymond
    European Journal of Combinatorics, Elsevier, 2018, 69, pp.49-53.
  15. 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.
  16. Strong immersion is a well-quasi-ordering for semicomplete digraphs
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Journal of Graph Theory, Wiley, 2018. <10.1002/jgt.22408>
  17. 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.
  18. Avoidability of circular formulas
    Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold
    Theoretical Computer Science, Elsevier, 2018, 726, pp.1-4.
  19. 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.
  20. 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.1-13.
  21. 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), paper 61.

2017

  1. Multigraphs without large bonds are wqo by contraction
    Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck, Marcin Kami´nskikami´nski
    Journal of Graph Theory, Wiley, 2017. <10.1002/jgt.22229>
  2. 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.
  3. 2-subcoloring is NP-complete for planar comparability graphs
    Pascal Ochem
    Information Processing Letters, Elsevier, 2017, 128, pp.46-48.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Colouring diamond-free graphs
    Konrad Dabrowski, François Dross, Daniël Paulusma
    Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.410-431.
  9. 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. 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.
  11. 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.
  12. 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.
  13. 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.
  14. Colorful paths for 3-chromatic graphs
    Nicolas Bousquet, Stéphane Bessy
    Discrete Mathematics, Elsevier, 2017, 340 (5), pp.1000-1007.
  15. 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.
  16. 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.
  17. 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.
  18. Bounds on the exponential domination number
    Stéphane Bessy, Pascal Ochem, Dieter Rautenbach
    Discrete Mathematics, Elsevier, 2017, 340 (3), pp.494-503.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. List Coloring with a Bounded Palette
    Marthe Bonamy, Ross J. Kang
    Journal of Graph Theory, Wiley, 2017, 84 (1), pp.93-103.
  27. 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.
  28. 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>
  29. Encoding toroidal triangulations
    Vincent Despré, Daniel Gonçalves, Benjamin Lévêque
    Discrete and Computational Geometry, Springer Verlag, 2017, 57 (57), pp.507-544.
  30. 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>
  31. 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.
  32. Computing a Clique Tree with the Algorithm Maximal Label Search
    Anne Berry, Geneviève Simonet
    Algorithms, MDPI AG, 2017, 10 (1), pp.#20.
  33. The Parameterized Complexity of Graph Cyclability
    Dimitrios M. Thilikos, Petr Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios Thilikos
    Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (1), pp.511 - 541.
  34. Avoidability of Formulas with Two Variables
    Pascal Ochem, Matthieu Rosenfeld
    The Electronic Journal of Combinatorics, Open Journal Systems, 2017, 14 (4), pp.#P4.30.
  35. 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.
  36. Low Polynomial Exclusion of Planar Graph Patterns
    Jean-Florent Raymond, Dimitrios M. Thilikos
    Journal of Graph Theory, Wiley, 2017, 84 (1), pp.26-44.
  37. An integer programming approach for the search of discretization orders in distance geometry problems
    Jérémy Omer, Douglas Gonçalves
    Optimization Letters, Springer Verlag, In press. <10.1007/s11590-017-1207-9>

2016

  1. (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.
  2. Orienting Triangulations
    Boris Albar, Daniel Gonçalves, Kolja Knauer
    Journal of Graph Theory, Wiley, 2016, 83 (4), pp.392-405.
  3. 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.
  4. Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
    Rodolphe Giroudeau, Guillerme Duvillié, Marin Bougeret, Rémi Watrigant
    Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, In press.
  5. 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.
  6. 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, Vol. 17 no. 3 (3), pp.131-146.
  7. 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.
  8. Parameterized certificate dispersal and its variants
    Valentin Garnero, Mathias Weller
    Theoretical Computer Science, Elsevier, 2016, 622, pp.66-78.
  9. 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. On interval representations of graphs
    Aquiles Braga de Queiroz, Valentin Garnero, Pascal Ochem
    Discrete Applied Mathematics, Elsevier, 2016, 202, pp.30-36.
  11. 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>
  12. Doubled patterns are 3-avoidable
    Pascal Ochem
    The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (1), pp.P1.19.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. Scattered packings of cycles
    Aistis Atminas, Marcin Kamiński, Jean-Florent Raymond
    Theoretical Computer Science, Elsevier, 2016, 647, pp.33 - 42.
  19. 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>
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.

2015

  1. 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.
  2. Planar Disjoint-Paths Completion
    Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos
    Algorithmica, Springer Verlag, 2015, 76 (2), pp.401-425.
  3. 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.
  4. 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.
  5. 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.
  6. Characterization of some binary words with few squares
    Golnaz Badkobeh, Pascal Ochem
    Theoretical Computer Science, Elsevier, 2015, 588, pp.73-80.
  7. 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.
  8. The role of planarity in connectivity problems parameterized by treewidth
    Julien Baste, Ignasi Sau
    Theoretical Computer Science, Elsevier, 2015, 570, pp.1-14.
  9. 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. 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.
  11. Excluding cycles with a fixed number of chords
    Pierre Aboulker, Nicolas Bousquet
    Discrete Applied Mathematics, Elsevier, 2015, 180, pp.11-24.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.

2014

  1. On the bend-number of planar and outerplanar graphs
    Daniel Heldt, Kolja Knauer, Torsten Ueckerdt
    Discrete Applied Mathematics, Elsevier, 2014, 179, pp.109-119.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. On the number of prime factors of an odd perfect number
    Pascal Ochem, Michaël Rao
    Mathematics of Computation, American Mathematical Society, 2014, 83 (289), pp.2435-2439.
  7. 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>
  8. Brooks’ theorem on powers of graphs
    Marthe Bonamy, Nicolas Bousquet
    Discrete Mathematics, Elsevier, 2014, 325, pp.12-16.
  9. 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.
  10. 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.
  11. 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.
  12. (Arc-)disjoint flows in networks
    Jørgen Bang-Jensen, Stéphane Bessy
    Theoretical Computer Science, Elsevier, 2014, 526, pp.28-40.
  13. Outerplanar obstructions for matroid pathwidth
    Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki
    Discrete Mathematics, Elsevier, 2014, 315, pp.95-101.
  14. Graphs with maximum degree Δ≥17 and maximum average degree less than 33 are list 22-distance (Δ+2)-colorable
    Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou
    Discrete Mathematics, Elsevier, 2014, 317, pp.19-32.
  15. Lift-contractions
    Petr A. Golovach, Daniël Paulusma, Marcin Kamiski, Dimitrios M. Thilikos
    European Journal of Combinatorics, Elsevier, 2014, 35, pp.286 - 296.
  16. Clique versus Independent Set
    Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
    European Journal of Combinatorics, Elsevier, 2014, 40, pp.73-92.
  17. 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.
  18. 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.
  19. Square roots of minor closed graph classes
    Nestor Nestoridis, Dimitrios M. Thilikos
    Discrete Applied Mathematics, Elsevier, 2014, 168, pp.34 - 39.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. Circle Graph Recognition in Time O(n+m)\alpha(n+m)
    Emeric Gioan, Christophe Paul, Marc Tedder, Derek Corneil
    Algorithmica, Springer Verlag, 2014, 69 (4), pp.789-788.
  26. 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.
  27. 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.
  28. 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.

2013

  1. Locally identifying coloring in bounded expansion classes of graphs
    Daniel Gonçalves, Aline Parreau, Alexandre Pinlou
    Discrete Applied Mathematics, Elsevier, 2013, 161 (18), pp.2946-2951.
  2. On approximating the $d$-girth of a graph
    David Peleg, Ignasi Sau, Mordechai Shalom
    Discrete Applied Mathematics, Elsevier, 2013, 161 (16-17), pp.2587-2596.
  3. On exact algorithms for the permutation CSP
    Eun Jung Kim, Daniel Gonçalves
    Theoretical Computer Science, Elsevier, 2013, 511, pp.109-116.
  4. Strong edge-colouring and induced matchings
    Hervé Hocquard, Pascal Ochem, Petru Valicov
    Information Processing Letters, Elsevier, 2013, 113 (19-21), pp.836-843.
  5. Optimizing the Graph Minors Weak Structure Theorem
    Archontia C. Giannopoulou, Dimitrios M. Thilikos
    Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2013, 27 (3), pp.1209-1227.
  6. Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$
    Hervé Hocquard, Mickaël Montassier
    Journal of Combinatorial Optimization, Springer Verlag, 2013, 26 (1), pp.152-160.
  7. Characterizing Graphs of Small Carving-Width
    Rémy Belmonte, Pim Van 'T Hof, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos
    Discrete Applied Mathematics, Elsevier, 2013, pp.Electronic Edition.
  8. Asymptotic enumeration of non-crossing partitions on surfaces
    Dimitrios M. Thilikos, Ignasi Sau, Juanjo Rué
    Discrete Mathematics, Elsevier, 2013, pp.635-649.
  9. Increasing the minimum degree of a graph by contractions
    Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos
    Theoretical Computer Science, Elsevier, 2013, 481, pp.74-84.
  10. Partitioning the arcs of a digraph into a star forests of the underlying graph with prescribed orientation properties
    Jørgen Bang-Jensen, Daniel Gonçalves, Anders Yeo
    Theoretical Computer Science, Elsevier, 2013, 475, pp.13-20.
  11. A Complexity Dichotomy for the Coloring of Sparse Graphs
    Louis Esperet, Mickaël Montassier, Pascal Ochem, Alexandre Pinlou
    Journal of Graph Theory, Wiley, 2013, 73 (1), pp.85-102.
  12. Vertex Partitions of Graphs into Cographs and Stars
    Paul Dorbec, Mickael Montassier, Pascal Ochem
    Journal of Graph Theory, Wiley, 2013, 75, pp.75-90.
  13. On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems
    Sylvain Guillemot, Frédéric Havet, Christophe Paul, Anthony Perez
    Algorithmica, Springer Verlag, 2013, 65 (4), pp.900-926.
  14. Polynomial kernels for Proper Interval Completion and related problems
    Stéphane Bessy, Anthony Perez
    Information and Computation, Elsevier, 2013, 231, pp.89-108.
  15. Enumerating the edge-colourings and total colourings of a regular graph
    Stéphane Bessy, Frédéric Havet
    Journal of Combinatorial Optimization, Springer Verlag, 2013, 25 (4), pp.523-535.
  16. Obtaining a Bipartite Graph by Contracting Few Edges
    Christophe Paul, Pinar Heggernes, Pim Van 'T Hof, Daniel Lokshtanov
    Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2013, 27 (4), pp.2143-215.
  17. Complements of nearly perfect graphs
    Andras Gyarfas, Zhentao Li, Raphael Machado, Andras Sebo, Stéphan Thomassé, Nicolas Trotignon, András Sebő
    The Electronic Journal of Combinatorics, Open Journal Systems, 2013, 4 (3), pp.299 - 310.

Communications internationales

2018

  1. 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. 10th International Colloquium on Graph Theory and combinatorics, 2018. <https://projet.liris.cnrs.fr/~icgt2018/>
  2. 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. 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, pp.148-155, 2018.
  3. Partial complementation of graphs
    Fedor Fomin, Petr Golovach, Torstein Strømme, Dimitrios M. Thilikos
    SWAT: Scandinavian Workshops on Algorithm Theory, Jun 2018, Malmö, Sweden. 16th Scandinavian Symposium and Workshops on Algorithm Theory, LIPIcs (101), pp.21:1--21:13, 2018.
  4. 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. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. <10.1137/1.9781611975031.12>

2017

  1. Contraction-Bidimensionality of Geometric Intersection Graphs
    Julien Baste, Dimitrios M. Thilikos
    IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.5:1--5:13, 2017.
  2. Triangle packing in (sparse) tournaments: approximation and kernelization *
    Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
    Kirk Pruhs; Christian Sohler. ESA: European Symposium on Algorithms, Sep 2017, Vienne, Austria. 25th Annual European Symposium on Algorithms, pp.1-23, 2017, Leibniz International Proceedings in Informatics.
  3. 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. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.10:1--10:13, 2018.
  4. 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. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.3:1--3:12, 2018.
  5. 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. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.4:1--4:12, 2018.
  6. Structured Connectivity Augmentation
    Fedor Fomin, Petr Golovach, Dimitrios M. Thilikos
    MFCS: Mathematical Foundations of Computer Science, Aug 2017, Aalborg, Denmark. 42nd International Symposium on Mathematical Foundations of Computer Science, 2017. <10.4230/LIPIcs.MFCS.2017.29>
  7. 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. Symmetry in Finite and Infinite Structures - Symmetry in finite models, 2017.
  8. 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. 28th International Workshop on Combinatorial Algorithms, pp.12, 2017.
  9. 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. 44th International Colloquium on Automata, Languages, and Programming, 80 (57), pp.1-15, 2017, Leibniz International Proceedings in Informatics (LIPIcs).
  10. 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. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (10520), pp.100-112, 2017.
  11. 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. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (10520), pp.88-99, 2017, WG 2017.
  12. Dushnik-Miller dimension of TD-Delaunay complexes
    Daniel Gonçalves, Lucas Isenmann
    EuroCG: European Workshop on Computational Geometry, Apr 2017, Malmo, Sweden. 33rd European Workshop on Computational Geometry, 2017.

2016

  1. 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. 10th International Conference on Combinatorial Optimization and Applications, LNCS (10043), pp.423-437, 2016, Combinatorial Optimization and Applications.
  2. 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. 4th International Workshop on graph theory, 2016. <http://bgw.labri.fr/2016/>
  3. 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. 4th International Workshop on Graph Theory, 2016. <http://bgw.labri.fr/2016/>
  4. Vertex-partitions of graphs
    Mickaël Montassier
    ICGCA: International Conference on Graph theory, Combinatorics and their Applications, Oct 2016, Jinhua, China. 2nd International Conference on Graph Theory, Combinatorics and Applications, 2016.
  5. 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. 11th International Symposium on Parameterized and Exact Computation, LIPIcs (63), pp.15:1--15:13, 2017.
  6. 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. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.26:1-26:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs).
  7. Avoidability of Formulas with Two Variables
    Pascal Ochem, Matthieu Rosenfeld
    DLT: Developments in Language Theory, Jul 2016, Montréal, Canada. 20th International Conference on Developments in Language Theory, LNCS (9840), pp.344-354, 2016, Developments in Language Theory.
  8. 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. 11th International Conference on Algorithmic Aspects of Information and Management, LNCS (9778), pp.53-64, 2017.
  9. 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. 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, LNCS (9941), pp.195-206, 2016, WG 2016.
  10. 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. 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, LNCS (9941), pp.74-84, 2016, Graph-Theoretic Concepts in Computer Science.
  11. 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. 2016.
  12. 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. 4th International Symposium on Combinatorial Optimization, LNCS (9849), pp.148-159, 2016, Combinatorial Optimization.
  13. Revival d'un challenge d'optimisation
    Eric Bourreau, Brett Choquet, Valentin Pollet, Jocelyn Thiebaut, Bruno Yun
    ROADEF: Recherche Opérationnelle et Aide à la Décision, Feb 2016, Compiègne, France. 17ème Conference ROADEF, 2016. <http://roadef2016.utc.fr>
  14. Colouring Diamond-free Graphs
    Konrad K. Dabrowski, François Dross, Daniël Paulusma
    SWAT: Scandinavian Workshops on Algorithm Theory, 2016, Reykjavik, Iceland. 15th Scandinavian Symposium and Workshops on Algorithm Theory, 53, pp.16:1--16:14, 2016.

2015

  1. 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. 13th International Workshop on Approximation and Online Algorithms, LNCS (9499), pp.122-132, 2016.
  2. 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. 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.35-46, 2016, Approximation and Online Algorithms.
  3. An O(log OPT)-approximation for covering and 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. Springer International Publishing, 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.122-132, 2016.
  4. 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. 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.158-169, 2016, Approximation and Online Algorithms.
  5. 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. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.30-42, 2015.
  6. 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. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.139-150, 2015.
  7. 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. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.78-89, 2015.
  8. Bidimensionality and Parameterized Algorithms
    Dimitrios M. Thilikos
    IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.1-16, 2015.
  9. 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. 8th European Conference on Combinatorics, Graph Theory and Applications, Electronic Notes in Discrete Mathematics (49), pp.269-275, 2015.
  10. 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. 8th European Conference on Combinatorics, Graph Theory and Applications, Electronic Notes in Discrete Mathematics (49), pp.197-201, 2015.
  11. 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. 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings, LNCS (9210), pp.189-201, 2015, Fundamentals of Computation Theory.
  12. 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. Springer, Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings, LNCS (9210), pp.243-254, 2015, Fundamentals of Computation Theory.
  13. 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 Symposium in Russia, Jul 2015, Listvyanka, Russia. Springer, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings, LNCS (9139), pp.143-156, 2015, Computer Science -- Theory and Applications.
  14. 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. 10th International Computer Science Symposium in Russia, LNCS (9139), pp.123-142, 2015.
  15. 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. Workshop on New Directions for the Tutte Polynomial: Extensions, Interrelations, and Applications, 2015. <https://tutte2015.ma.rhul.ac.uk>
  16. 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. 2015. <https://conferences.matheo.si/event/6/page/12>
  17. 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. 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, 2015. <http://ctw2015.eng.marmara.edu.tr>
  18. 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. 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, 2015. <http://ctw2015.eng.marmara.edu.tr>
  19. Orienting triangulations
    Boris Albar, Daniel Gonçalves, Kolja Knauer
    EuroCG: European Workshop on Computational Geometry, Mar 2015, Ljubljana, Slovenia. 31st European Workshop on Computational Geometry, EuroCG 2015. <http://eurocg15.fri.uni-lj.si>
  20. 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. 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). <10.1137/1.9781611973761.2>
  21. 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. 26th International Workshop on Combinatorial Algorithms, LNCS (9538), pp.100-111, 2016, Combinatorial Algorithms.

2014

  1. 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. 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, LNCS (8894), pp.97-109, 2014, Parameterized and Exact Computation.
  2. 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. 9th International Symposium on Parameterized and Exact Computation, LNCS (8894), pp.63-74, 2014, Parameterized and Exact Computation.
  3. 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. 19th Annual European Symposium on Algorithms, LNCS (8737), pp.492-504, 2014.
  4. 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. LNCS (8635), pp.299-310, 2014, Mathematical Foundations of Computer Science.
  5. 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. Siam, 14th SIAM International Conference on Data Mining, pp.668-676, 2014.
  6. 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. Twenty-Sixth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-14), July 29–31, 2014 in Québec City, Québec, Canada., 2014.
  7. 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. 9th International colloquium on graph theory and combinatorics, June 30-July 4, 2014, 2014.
  8. 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. 9th International colloquium on graph theory and combinatorics, 2014.
  9. 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. 9th International colloquium on graph theory and combinatorics, 2014.
  10. Recognition of dynamic circle graphs
    Christophe Crespelle, Emeric Gioan, Christophe Paul
    ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International colloquium on graph theory and combinatorics, 2014. <http://oc.inpg.fr/conf/icgt2014/>
  11. 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. 9th International colloquium on graph theory and combinatorics, 2014.
  12. 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. 9th International colloquium on graph theory and combinatorics, 2014. <http://oc.inpg.fr/conf/icgt2014/>
  13. 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. 9th International colloquium on graph theory and combinatorics, 2014.
  14. 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. 9th International colloquium on graph theory and combinatorics, 2014. <http://oc.inpg.fr/conf/icgt2014/>
  15. 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. 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, LNCS (8747), pp.201-213, 2014, WG 2014.
  16. 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. 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, LNCS (8747), pp.139-151, 2014, Graph-Theoretic Concepts in Computer Science.
  17. 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. 31st International Symposium on Theoretical Aspects of Computer Science, LIPIcs (25), pp.312-324, 2014.
  18. 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. 40th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS (8327), pp.293-305, 2014.
  19. 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. 40th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS (8327), pp.150-161, 2014.
  20. 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. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1424-1432, 2014, Proceedings of SODA '14.
  21. Entropy compression method and graph coloring problems
    Mickaël Montassier
    C&C: Cycles and Colourings, 2014, Novy Smokovec, Slovakia. 23rd, 2014.

2013

  1. Theory and Applications of Bidimensionality
    Dimitrios M. Thilikos
    COCOA: Conference on Combinatorial Optimization and Applications, Dec 2013, Chengdu, China. 7th Annual International Conference on Combinatorial Optimization and Applications, 2013, Invited Lectures. <10.1007/978-3-319-03780-6>
  2. Skull Shapes and Oriented Matroids
    Emeric Gioan
    FMMIAM: French-Mexican Meeting on Industrial and Applied Mathematics, Nov 2013, Tabasco, Mexico. 2013. <http://paginas.matem.unam.mx/fmmiam/>
  3. Polynomial Gap Extensions of the Erdős-Pósa Theorem
    Jean-Florent Raymond, Dimitrios M. Thilikos
    EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. Springer, 7th European Conference on Combinatorics, Graph Theory and Applications, 16, pp.13-18, 2013, CRM Series.
  4. Strong chromatic index of planar graphs with large girth
    Arnaud Pêcher, Mickaël Montassier, André Raspaud
    EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. 7th European Conference on Combinatorics, Graph Theory and Applications, pp.265-270, 2013.
  5. Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions
    Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar
    ICALP: International Colloquium on Automata, Languages and Programming, Jul 2013, Riga, Latvia. 40th International Colloquium on Automata, Languages, and Programming, LNCS (7965), pp.613-624, 2013.
  6. Excluding Graphs as Immersions in Surface Embedded Graphs
    Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos
    WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2013, Lübeck, Germany. 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, LNCS (8165), pp.274-285, 2013, Graph-Theoretic Concepts in Computer Science.
  7. A linear kernel for planar red-blue dominating set
    Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos
    CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2013, Enschede, Netherlands. 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.117-120, 2013.
  8. Too many triangles
    Boris Albar, Daniel Gonçalves
    LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, Apr 2013, Playa del Carmen, Mexico. VII Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS) April 22-26, 2013 Playa del Carmen, Mexico, 44, pp.293-297, 2013, Electronic Notes in Discrete Mathematics.
  9. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
    Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
    STACS: Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. 30th Symposium on Theoretical Aspects of Computer Science, LIPIcs (20), pp.92-103, 2013.
  10. Recoloring bounded treewidth graphs
    Marthe Bonamy, Nicolas Bousquet
    LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, 2013, Playa del Carmen, Mexico. VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS) April 22-26, 2013 Playa del Carmen, Mexico, 44, pp.293-297, 2013, Electronic Notes in Discrete Mathematics.
  11. Adjacent vertex-distinguishing edge coloring of graphs
    Marthe Bonamy, Nicolas Bousquet, Hervé Hocquard
    EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2013, Pise, Italy. pp.313-318, 2013, The Seventh European Conference on Combinatorics, Graph Theory and Applications.
  12. Planar graphs with Δ ≥ 8 are (Δ + 1)-edge-choosable
    Marthe Bonamy
    EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2013, Pise, Italy. pp.241-244, 2013, The Seventh European Conference on Combinatorics, Graph Theory and Applications.

Mots-clés

Algorithmique de Graphes, Théorie des Graphes, Combinatoire

Dernière mise à jour le 27/06/2018