Computational complexity of some connectivity problems
2012/07/D/ST6/02432
Keywords
Descriptors
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST1_14: Kombinatoryka
- ST1_15: Matematyczne aspekty informatyki
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: 3
Call
SONATA 4 – announced on 2012-09-15
- Amount awarded
- 398 960 PLN
- Project start date
- 2013-07-09
- Project end date
- 2016-07-08
- Project duration
- 36 months (the same as in the proposal)
- Project status
- Project settled
Equipment purchased [PL]
- Sprzęt komputerowy (2 pcs). Cost: 10 000 PLN
Information in the final report
Publication in academic press/journals (3)
-
Induced minors and well-quasi-ordering
- Authors:
- Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
- Academic press:
- Electronic Notes in Discrete Mathematics (year: 2015, volume: 49, pages: 197-201), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.endm.2015.06.029 – link to the publication
-
Forbidding Kuratowski Graphs as Immersions
- Authors:
- Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos
- Academic press:
- Journal of Graph Theory (year: 2015, volume: 78, pages: 43-60), Publisher: Wiley
- Status:
- Published
- DOI:
- 10.1002/jgt.21790 – link to the publication
-
Minimal Disconnected Cuts in Planar Graphs
- Authors:
- Marcin Kamiński, Daniël Paulusma, Anthony Stewart , Dimitrios M. Thilikos
- Academic press:
- Fundamentals of Computation Theory (year: 2015, volume: 9210, pages: 243-254), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/978-3-319-22177-9_19 – link to the publication
Articles in post-conference publications (3)
-
Reconfiguring Independent Sets in Claw-Free Graphs
- Authors:
- Paul Bonsma, Marcin Kamiński, Marcin Wrochna
- Conference:
- Scandinavian Workshop on Algorithm Theory (year: 2014, pages: 86-97), Publisher: Springer
- Date:
- conference 2-4.07.2014
- Status:
- Published
- DOI:
- link to the publication
-
Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
- Authors:
- Rémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma
- Conference:
- Mathematical Foundations of Computer Science (year: 2014, pages: 57-68), Publisher: Springer
- Date:
- conference 25-29.08.2014
- Status:
- Published
- DOI:
- link to the publication
-
The Parameterized Complexity of Graph Cyclability
- Authors:
- Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos
- Conference:
- European Symposium on Algorithms (year: 2014, pages: 492-504), Publisher: Springer
- Date:
- conference 9,2014
- Status:
- Published
- DOI:
- link to the publication