Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Algorytmy parametryzowane w problemach grafowych oraz wyszukiwaniu wzorca permutacji.

2012/05/D/ST6/03214

Słowa kluczowe:

algorytmy parametryzowane szerokość drzewiasta algorytmy grafowe wyszukiwanie wzorca permutacji

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier

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 Marek Cygan 

Liczba wykonawców projektu: 2

Konkurs: SONATA 3 - ogłoszony 2012-03-15

Przyznana kwota: 428 600 PLN

Rozpoczęcie projektu: 2013-02-04

Zakończenie projektu: 2017-02-03

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

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Komputer przenośny typu notebook.. Za kwotę 6 000 PLN
  2. Komputer stacjonarny. Za kwotę 4 000 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (6)
  • Teksty w publikacjach pokonferencyjnych (7)
  • Publikacje książkowe (1)
  1. Faster deterministic Feedback Vertex Set
    Autorzy:
    Tomasz Kociumaka, Marcin Pilipczuk
    Czasopismo:
    Information Processing Letters (rok: 2014, tom: 114 (10), strony: 556-560), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ipl.2014.05.001 - link do publikacji
  2. A tight lower bound for Vertex Planarization on graphs of bounded treewidth
    Autorzy:
    Marcin Pilipczuk
    Czasopismo:
    Discrete Applied Mathematics (rok: 2016, tom: -, strony: ), Wydawca: Elsevier
    Status:
    Przyjęta do publikacji
    Doi:
    10.1016/j.dam.2016.05.019 - link do publikacji
  3. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth
    Autorzy:
    Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Czasopismo:
    Information and Computation (speciall issue for MFCS 2014) , Wydawca: Elsevier
    Status:
    Przyjęta do publikacji
    Doi:
    brak - link do publikacji
  4. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
    Autorzy:
    Hans Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Czasopismo:
    Information and Computation , Wydawca: Elsevier
    Status:
    Przyjęta do publikacji
    Doi:
    10.1016/j.ic.2014.12.008 - link do publikacji
  5. Kernelization lower bound for Permutation Pattern Matching
    Autorzy:
    Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
    Czasopismo:
    Information Processing Letters (rok: 2015, tom: 115 (5), strony: 527-531), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ipl.2015.01.001 - link do publikacji
  6. Polynomial Kernelization for Removing Induced Claws and Diamonds
    Autorzy:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Czasopismo:
    Theory of Computing Systems (rok: 2016, tom: nie dotyczy, strony: 45313), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-016-9689-x - link do publikacji
  1. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth
    Autorzy:
    Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Konferencja:
    Mathematical Foundations of Computer Science 2014 - 39th International Symposium, (MFCS 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 25-29.08.2014
    Status:
    Opublikowana
  2. Lower Bounds for Approximation Schemes for Closest String
    Autorzy:
    Marek Cygan, Daniel Loskhtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Konferencja:
    15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). (rok: 2016, ), Wydawca: LIPIcs: Leibniz International |Proceedings in Informatics
    Data:
    konferencja 22-24.06.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  3. Approximation and Kernelization for Chordal Vertex Deletion
    Autorzy:
    Bart Jansen, Marcin Pilipczuk
    Konferencja:
    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) (rok: 2017, ), Wydawca: SIAM
    Data:
    konferencja 16-19.01.2017
    Status:
    Opublikowana
  4. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
    Autorzy:
    Hans Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Konferencja:
    40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 8-12.07.2013
    Status:
    Opublikowana
    Doi:
    link do publikacji
  5. Fast hamiltonicity checking via bases of perfect matchings
    Autorzy:
    Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Konferencja:
    45th ACM Symposium on Theory of Computing (STOC 2013) (rok: 2013, ), Wydawca: ACM
    Data:
    konferencja 1-4.06.2013
    Status:
    Opublikowana
    Doi:
    link do publikacji
  6. Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
    Autorzy:
    Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach, Michal Pilipczuk
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 1,2016
    Status:
    Opublikowana
  7. Polynomial Kernelization for Removing Induced Claws and Diamonds
    Autorzy:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Konferencja:
    Graph-Theoretic Concepts in Computer Science - 41st International Workshop (WG 2015) (rok: 2015, ), Wydawca: Springer (LNCS)
    Data:
    konferencja 17-19.06.2015
    Status:
    Opublikowana
  1. monografia naukowa
    Autorzy:
    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
    Książka:
    Parameterized Algorithms (rok: 2015, tom: 1, strony: 3-555), Wydawca: Springer
    Status:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy