Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Optymalność w złożoności parametryzowanej

2013/11/D/ST6/03073

Słowa kluczowe:

złożoność parametryzowana algorytmika ustalonego parametru program optymalności hipoteza czasu wykładniczego

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 Michał Pilipczuk 

Liczba wykonawców projektu: 2

Konkurs: SONATA 6 - ogłoszony 2013-09-16

Przyznana kwota: 386 320 PLN

Rozpoczęcie projektu: 2014-10-01

Zakończenie projektu: 2017-09-30

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

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Laptop dla drugiego wykonawcy. Za kwotę 5 000 PLN
  2. Laptop dla kierownika projektu. Za kwotę 5 000 PLN
  3. Komputer stacjonarny dla kierownika projektu. Za kwotę 4 000 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (17)
  • Teksty w publikacjach pokonferencyjnych (20)
  1. Below all subsets for Minimal Connected Dominating Set
    Autorzy:
    Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh
    Czasopismo:
    SIAM Journal on Discrete Mathematics (SIDMA) (rok: 2018, tom: 32(3), strony: 2332-2345), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Opublikowana
    Doi:
    10.1137/17M1138753 - link do publikacji
  2. Edge Bipartization faster than 2^k
    Autorzy:
    Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
    Czasopismo:
    Algorithmica (rok: 2019, tom: 81(3), strony: 917-966), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-017-0319-z - link do publikacji
  3. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
    Autorzy:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Czasopismo:
    ACM Transactions on Algorithms (TALG) (rok: 2018, tom: 14(3), strony: 38:1-38:31), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3196276 - link do publikacji
  4. 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: 2017, tom: 60(4), strony: 615-636), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-016-9689-x - link do publikacji
  5. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Autorzy:
    Linear kernels for edge deletion problems to immersion-closed graph classes
    Czasopismo:
    wersja czasopismowa pracy z ICALP 2017, wysłana do recenzji do czasopisma SIAM Journal on Discrete Mathematics (), Wydawca: -
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  6. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
    Autorzy:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Czasopismo:
    wersja czasopismowa pracy z ESA 2018, wysłana do recenzji do czasopisma Algorithmica , Wydawca: -
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  7. On space efficiency of algorithms working on structural decompositions of graphs
    Autorzy:
    Michał Pilipczuk, Marcin Wrochna
    Czasopismo:
    ACM Transactions on Computation Theory (TOCT) (rok: 2018, tom: 9(4), strony: 18:1-18:36), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3154856 - link do publikacji
  8. Turing kernelization for finding long paths in graph classes excluding a topological minor
    Autorzy:
    Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
    Czasopismo:
    Algorithmica (rok: 2019, tom: Online First, strony: 11689), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-019-00614-4 - link do publikacji
  9. Cutwidth: obstructions and algorithmic aspects
    Autorzy:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Czasopismo:
    Algorithmica (rok: 2019, tom: 81(2), strony: 557-588), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-018-0424-7 - link do publikacji
  10. Hardness of approximation for Strip Packing
    Autorzy:
    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk
    Czasopismo:
    ACM Transactions on Computation Theory (TOCT) (rok: 2017, tom: 9(3), strony: 14:1--14:7), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3092026 - link do publikacji
  11. A polynomial kernel for Trivially Perfect Editing
    Autorzy:
    Pål Grønås Drange, Michał Pilipczuk
    Czasopismo:
    Algorithmica (rok: 2018, tom: 80(12), strony: 3481-3524), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-017-0401-6 - link do publikacji
  12. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
    Autorzy:
    Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna
    Czasopismo:
    ACM Transactions on Algorithms (TALG) (rok: 2018, tom: 14(3), strony: 34:1--34:45), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3186898 - link do publikacji
  13. Tight lower bounds for the complexity of Multicoloring
    Autorzy:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Czasopismo:
    ACM Transactions on Computation Theory (TOCT) (rok: 2019, tom: 11(3), strony: 13:1-13:19), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3313906 - link do publikacji
  14. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    Autorzy:
    Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Czasopismo:
    wersja konferencyjna pracy z FOCS 2016, złożona do recenzji w czasopiśmie SIAM Journal on Computing , Wydawca: -
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  15. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
    Autorzy:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk
    Czasopismo:
    wersja czasopismowa pracy opublikowanej na SODA 2016, złożona do recenzji w czasopiśmie ACM Transactions on Algorithms , Wydawca: -
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  16. Hardness of approximation for H-free edge modification problems
    Autorzy:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
    Czasopismo:
    ACM Transactions on Computation Theory (TOCT) (rok: 2018, tom: 10(2), strony: 9:1-9:32), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3196834 - link do publikacji
  17. Strong immersion is a well-quasi-ordering for semi-complete digraphs
    Autorzy:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Czasopismo:
    Journal of Graph Theory (rok: 2019, tom: 90(4), strony: 484-496), Wydawca: Wiley
    Status:
    Opublikowana
    Doi:
    10.1002/jgt.22408 - link do publikacji
  1. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
    Autorzy:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Konferencja:
    26th Annual European Symposium on Algorithms, ESA 2018 (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 20-22.08.2018
    Status:
    Opublikowana
    Doi:
    link do publikacji
  2. Tight lower bounds for the complexity of multicoloring
    Autorzy:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Konferencja:
    25th Annual European Symposium on Algorithms, ESA 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 4-6.09.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  3. Fast algorithms for parameterized problems with relaxed disjointness constraint
    Autorzy:
    Ariel Gabizon, Daniel Lokshtanov, Michał Pilipczuk
    Konferencja:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Opublikowana
  4. Lower bounds for approximation schemes for Closest String
    Autorzy:
    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Konferencja:
    15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 22-24.06.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  5. On Directed Feedback Vertex Set parameterized by treewidth
    Autorzy:
    Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Konferencja:
    44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 27-29.06.2018
    Status:
    Opublikowana
    Doi:
    link do publikacji
  6. On space efficiency of algorithms working on structural decompositions of graphs
    Autorzy:
    Michał Pilipczuk, Marcin Wrochna
    Konferencja:
    33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 17-20.02.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  7. Turing kernelization for finding long paths in graph classes excluding a topological minor
    Autorzy:
    Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
    Konferencja:
    12th International Symposium on Parameterized and Exact Computation, IPEC 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 6-8.09.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  8. Approximation and parameterized algorithms for geometric independent set with shrinking
    Autorzy:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Konferencja:
    42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 21-25.08.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  9. Edge Bipartization faster than 2^k
    Autorzy:
    Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
    Konferencja:
    11th International Symposium on Parameterized and Exact Computation, IPEC 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 24-26.08.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  10. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
    Autorzy:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Konferencja:
    44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  11. Hardness of approximation for H-free edge modification problems
    Autorzy:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
    Konferencja:
    19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  12. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
    Autorzy:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk
    Konferencja:
    27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 10-12.01.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  13. A polynomial kernel for Trivially Perfect Editing
    Autorzy:
    Pål Grønås Drange, Michał Pilipczuk
    Konferencja:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Opublikowana
  14. Cutwidth: obstructions and algorithmic aspects
    Autorzy:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Konferencja:
    11th International Symposium on Parameterized and Exact Computation, IPEC 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 24-26.08.2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  15. Linear kernels for edge deletion problems to immersion-closed graph classes
    Autorzy:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Konferencja:
    44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  16. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
    Autorzy:
    Dániel Marx, Michał Pilipczuk
    Konferencja:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Opublikowana
  17. Polynomial kernelization for removing induced claws and diamonds
    Autorzy:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Konferencja:
    41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 17-19.06.2015
    Status:
    Opublikowana
  18. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
    Autorzy:
    Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna
    Konferencja:
    28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (rok: 2017, ), Wydawca: SIAM
    Data:
    konferencja 16-19.01.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  19. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
    Autorzy:
    Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Konferencja:
    59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (rok: 2018, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 7-9.10.2018
    Status:
    Opublikowana
    Doi:
    link do publikacji
  20. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    Autorzy:
    Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Konferencja:
    IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 (rok: 2016, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 9-11.10.2016
    Status:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy