Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Computational complexity of some connectivity problems

2012/07/D/ST6/02432

Keywords:

graph algorithms connectivity paremeterized complexity planar graphs

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_14: Discrete mathematics and combinatorics
  • ST1_15: Mathematical aspects of computer science

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 hab. Marcin Kamiński 

Number of co-investigators in the project: 3

Call: SONATA 4 - announced on 2012-09-15

Amount awarded: 398 960 PLN

Project start date (Y-m-d): 2013-07-09

Project end date (Y-m-d): 2016-07-08

Project duration:: 36 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Sprzęt komputerowy (2 szt.) (10 000 PLN)

Information in the final report

  • Publication in academic press/journals (3)
  • Articles in post-conference publications (3)
  1. Induced minors and well-quasi-ordering
    Authors:
    Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
    Academic press:
    Electronic Notes in Discrete Mathematics (rok: 2015, tom: 49, strony: 197-201), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.endm.2015.06.029 - link to the publication
  2. Minimal Disconnected Cuts in Planar Graphs
    Authors:
    Marcin Kamiński, Daniël Paulusma, Anthony Stewart , Dimitrios M. Thilikos
    Academic press:
    Fundamentals of Computation Theory (rok: 2015, tom: 9210, strony: 243-254), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/978-3-319-22177-9_19 - link to the publication
  3. Forbidding Kuratowski Graphs as Immersions
    Authors:
    Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos
    Academic press:
    Journal of Graph Theory (rok: 2015, tom: 78, strony: 43-60), Wydawca: Wiley
    Status:
    Published
    DOI:
    10.1002/jgt.21790 - link to the publication
  1. Reconfiguring Independent Sets in Claw-Free Graphs
    Authors:
    Paul Bonsma, Marcin Kamiński, Marcin Wrochna
    Conference:
    Scandinavian Workshop on Algorithm Theory (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2014
    Status:
    Published
    DOI:
    link to the publication
  2. 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 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 25-29.08.2014
    Status:
    Published
    DOI:
    link to the publication
  3. The Parameterized Complexity of Graph Cyclability
    Authors:
    Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos
    Conference:
    European Symposium on Algorithms (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 9,2014
    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