Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

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

2013/11/N/ST6/02706

Keywords:

graph theory algorithms order theory

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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

woj. 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 (Y-m-d): 2014-07-15

Project end date (Y-m-d): 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)
  • Articles in post-conference publications (5)
  1. 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 (rok: 2018, tom: 32(2), strony: 2302-2312), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/17M1153169 - link to the publication
  2. An edge variant of the Erdős-Pósa property
    Authors:
    Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos
    Academic press:
    Discrete Mathematics (rok: 2016, tom: 339, strony: 2027-2035), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2016.03.004 - link to the publication
  3. 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 (rok: 2017, tom: 65, strony: 154-167), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.05.009 - link to the publication
  4. Polynomial expansion and sublinear separators
    Authors:
    Louis Esperet and Jean-Florent Raymond
    Academic press:
    European Journal of Combinatorics (rok: 2018, tom: 69, strony: 49-53), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.09.003 - link to the publication
  5. 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 (rok: 2017, tom: unknown, strony: 45318), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0313-5 - link to the publication
  6. Cutwidth: obstructions and algorithmic aspects
    Authors:
    Archontia Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna
    Academic press:
    Algorithmica (rok: 2018, ), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-018-0424-7 - link to the publication
  7. 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 (rok: 2019, tom: 134, strony: 110-142), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jctb.2018.05.005 - link to the publication
  8. Scattered packings of cycles
    Authors:
    Aistis Atminas, Marcin Kamiński, and Jean-Florent Raymond
    Academic press:
    Theoretical Computer Science (rok: 2016, tom: 647, strony: 33–42), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.07.021 - link to the publication
  9. Hitting minors, subdivisions, and immersions in tournaments
    Authors:
    Jean-Florent Raymond
    Academic press:
    Discrete Mathematics & Theoretical Computer Science (rok: 2018, tom: 20(1), strony: 45300), Wydawca: Discrete Mathematics & Theoretical Computer Science
    Status:
    Published
    DOI:
    10.23638/DMTCS-20-1-5 - link to the publication
  10. 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 (rok: 2017, tom: 65, strony: 106-121), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2017.04.011 - 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 (rok: 2018, tom: 248, strony: 18-27), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2016.12.025 - link to the publication
  12. Well-quasi-ordering H-contraction-free graphs
    Authors:
    Marcin Kamiński, Jean-Florent Raymond and Théophile Trunck
    Academic press:
    Discrete Applied Mathematics (rok: 2018, tom: 248, strony: 18-27), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2017.02.018 - link to the publication
  1. 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 (rok: 2016, ), Wydawca: Leibniz International Proceedings in Informatics
    Data:
    konferencja 24-26 / 08
    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 (rok: 2016, ), Wydawca: Springer, Berlin, Heidelberg
    Data:
    konferencja 22-24 / 06
    Status:
    Published
    DOI:
    link to the publication
  3. 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 (rok: 2017, ), Wydawca: Leibniz International Proceedings in Informatics
    Data:
    konferencja 10/07/17 - 14/07/17
    Status:
    Published
    DOI:
    link to the publication
  4. 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) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 20-24/08/2018
    Status:
    Published
    DOI:
    link to the publication
  5. 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 (rok: 2015, ), Wydawca: Lecture Notes in Computer Science
    Data:
    konferencja 17-17 september
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy