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
Principal investigator (from the host institution)
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)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
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
-
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