Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Złożoność obliczeniowa problemów spójności w grafach

2012/07/D/ST6/02432

Słowa kluczowe:

algorytmy grafowe spójność złożoność parametryzowana grafy planarne

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_14: Kombinatoryka
  • ST1_15: Matematyczne aspekty informatyki

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Marcin Kamiński 

Liczba wykonawców projektu: 3

Konkurs: SONATA 4 - ogłoszony 2012-09-15

Przyznana kwota: 398 960 PLN

Rozpoczęcie projektu: 2013-07-09

Zakończenie projektu: 2016-07-08

Planowany czas trwania projektu: 36 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Zakupiona aparatura

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

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (3)
  • Teksty w publikacjach pokonferencyjnych (3)
  1. Induced minors and well-quasi-ordering
    Autorzy:
    Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
    Czasopismo:
    Electronic Notes in Discrete Mathematics (rok: 2015, tom: 49, strony: 197-201), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.endm.2015.06.029 - link do publikacji
  2. Minimal Disconnected Cuts in Planar Graphs
    Autorzy:
    Marcin Kamiński, Daniël Paulusma, Anthony Stewart , Dimitrios M. Thilikos
    Czasopismo:
    Fundamentals of Computation Theory (rok: 2015, tom: 9210, strony: 243-254), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/978-3-319-22177-9_19 - link do publikacji
  3. Forbidding Kuratowski Graphs as Immersions
    Autorzy:
    Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos
    Czasopismo:
    Journal of Graph Theory (rok: 2015, tom: 78, strony: 43-60), Wydawca: Wiley
    Status:
    Opublikowana
    Doi:
    10.1002/jgt.21790 - link do publikacji
  1. Reconfiguring Independent Sets in Claw-Free Graphs
    Autorzy:
    Paul Bonsma, Marcin Kamiński, Marcin Wrochna
    Konferencja:
    Scandinavian Workshop on Algorithm Theory (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2014
    Status:
    Opublikowana
  2. Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
    Autorzy:
    Rémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma
    Konferencja:
    Mathematical Foundations of Computer Science (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 25-29.08.2014
    Status:
    Opublikowana
  3. The Parameterized Complexity of Graph Cyclability
    Autorzy:
    Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos
    Konferencja:
    European Symposium on Algorithms (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 9,2014
    Status:
    Opublikowana