Graphs within graphs: from well-quasi-orders to algorithms

2013/11/N/ST6/02706

Keywords

Descriptors

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier

Panel

ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

Voivodeship: mazowieckie

Other projects carried out by the institution »

Principal investigator (from the host institution)

dr Jean-Florent Raymond

Number of co-investigators in the project: 2

Call

PRELUDIUM 6 – announced on 2013-09-16

Amount awarded
149 890 PLN
Project start date
2014-07-15
Project end date
2017-07-14
Project duration
36 months (the same as in the proposal)
Project status
Project settled

Information in the final report

Publication in academic press/journals (12)

  1. Hitting minors, subdivisions, and immersions in tournaments

    Authors:
    Jean-Florent Raymond
    Academic press:
    Discrete Mathematics & Theoretical Computer Science (year: 2018, volume: 20(1), pages: 46031), Publisher: Discrete Mathematics & Theoretical Computer Science
    Status:
    Published
    DOI:
    10.23638/DMTCS-20-1-5 – link to the publication
  2. Polynomial expansion and sublinear separators

    Authors:
    Louis Esperet and Jean-Florent Raymond
    Academic press:
    European Journal of Combinatorics (year: 2018, volume: 69, pages: 49-53), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.09.003 – link to the publication
  3. A tight Erdős-Pósa function for wheel minors

    Authors:
    Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, and Ignasi Sau
    Academic press:
    SIAM Journal on Discrete Mathematics (year: 2018, volume: 32(2), pages: 2302-2312), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/17M1153169 – link to the publication
  4. An edge variant of the Erdős-Pósa property

    Authors:
    Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos
    Academic press:
    Discrete Mathematics (year: 2016, volume: 339, pages: 2027-2035), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2016.03.004 – link to the publication
  5. Induced minors and well-quasi-ordering

    Authors:
    Jaroslaw Błasiok, Marcin Kamiński, Jean-Florent Raymond and Théophile Trunck
    Academic press:
    Journal of Combinatorial Theory, Series B (year: 2019, volume: 134, pages: 110-142), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jctb.2018.05.005 – link to the publication
  6. Scattered packings of cycles

    Authors:
    Aistis Atminas, Marcin Kamiński, and Jean-Florent Raymond
    Academic press:
    Theoretical Computer Science (year: 2016, volume: 647, pages: 33–42), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.07.021 – link to the publication
  7. Cutwidth: obstructions and algorithmic aspects

    Authors:
    Archontia Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna
    Academic press:
    Algorithmica (year: 2018, volume: 0, pages: 11689), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-018-0424-7 – link to the publication
  8. Well-quasi-ordering H-contraction-free graphs

    Authors:
    Marcin Kamiński, Jean-Florent Raymond and Théophile Trunck
    Academic press:
    Discrete Applied Mathematics (year: 2018, volume: 248, pages: 18-27), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2017.02.018 – link to the publication
  9. Minors in graphs of large θr-girth

    Authors:
    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos
    Academic press:
    European Journal of Combinatorics (year: 2017, volume: 65, pages: 106-121), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.04.011 – link to the publication
  10. Packing and covering immersion models of planar subcubic graphs

    Authors:
    Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos
    Academic press:
    European Journal of Combinatorics (year: 2017, volume: 65, pages: 154-167), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.05.009 – link to the publication
  11. Recent techniques and results on the Erdős-Pósa property

    Authors:
    Jean-Florent Raymond and Dimitrios M. Thilikos
    Academic press:
    Discrete Applied Mathematics (year: 2018, volume: 248, pages: 18-27), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2016.12.025 – link to the publication
  12. An O(log OPT)-approximation for covering/packing minor models of θr

    Authors:
    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos
    Academic press:
    Algorithmica (year: 2017, volume: unknown, pages: 46049), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0313-5 – link to the publication

Articles in post-conference publications (5)

  1. An O(log OPT)-approximation for covering/packing minor models of θr

    Authors:
    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos
    Conference:
    13th Workshop on Approximation and Online Algorithms (year: 2015, pages: 122-132), Publisher: Lecture Notes in Computer Science
    Date:
    conference 17-17 september
    Status:
    Published
    DOI:
    link to the publication
  2. Packing and covering immersion models of planar subcubic graphs

    Authors:
    Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos
    Conference:
    WG2016, International Workshop on Graph-Theoretic Concepts in Computer Science (year: 2016, pages: 74-84), Publisher: Springer, Berlin, Heidelberg
    Date:
    conference 22-24 / 06
    Status:
    Published
    DOI:
    link to the publication
  3. On the tractability of optimization problems in H-graphs

    Authors:
    Fedor V. Fomin, Petr Golovach, and Jean-Florent Raymond
    Conference:
    European Symposium on Algorithms (ESA) (year: 2018, pages: 46036), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 20-24/08/2018
    Status:
    Published
    DOI:
    link to the publication
  4. Linear kernels for edge deletion problems to immersion-closed graph classes

    Authors:
    Archontia Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna
    Conference:
    International Colloquium on Automata, Languages, and Programming (year: 2017, pages: 57:1--57:15), Publisher: Leibniz International Proceedings in Informatics
    Date:
    conference 10/07/17 - 14/07/17
    Status:
    Published
    DOI:
    link to the publication
  5. Cutwidth: obstructions and algorithmic aspects

    Authors:
    Archontia Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna
    Conference:
    IPEC 2016, 11th International Symposium on Parameterized and Exact Computation (year: 2016, pages: 15:1-15:13), Publisher: Leibniz International Proceedings in Informatics
    Date:
    conference 24-26 / 08
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski