Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Parameterized algorithms in graph problems and permutation pattern matching.

2012/05/D/ST6/03214

Keywords:

parameterized algorithms treewidth graph algorithms permutation pattern matching

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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

Number of co-investigators in the project: 2

Call: SONATA 3 - announced on 2012-03-15

Amount awarded: 428 600 PLN

Project start date (Y-m-d): 2013-02-04

Project end date (Y-m-d): 2017-02-03

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

Project status: Project settled

Equipment purchased [PL]

  1. Komputer przenośny typu notebook. (6 000 PLN)
  2. Komputer stacjonarny (4 000 PLN)

Information in the final report

  • Publication in academic press/journals (6)
  • Articles in post-conference publications (7)
  • Book publications / chapters in book publications (1)
  1. Faster deterministic Feedback Vertex Set
    Authors:
    Tomasz Kociumaka, Marcin Pilipczuk
    Academic press:
    Information Processing Letters (rok: 2014, tom: 114 (10), strony: 556-560), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2014.05.001 - link to the publication
  2. A tight lower bound for Vertex Planarization on graphs of bounded treewidth
    Authors:
    Marcin Pilipczuk
    Academic press:
    Discrete Applied Mathematics (rok: 2016, tom: -, strony: ), Wydawca: Elsevier
    Status:
    Accepted for publication
    DOI:
    10.1016/j.dam.2016.05.019 - link to the publication
  3. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth
    Authors:
    Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Academic press:
    Information and Computation (speciall issue for MFCS 2014) , Wydawca: Elsevier
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  4. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
    Authors:
    Hans Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Academic press:
    Information and Computation , Wydawca: Elsevier
    Status:
    Accepted for publication
    DOI:
    10.1016/j.ic.2014.12.008 - link to the publication
  5. Kernelization lower bound for Permutation Pattern Matching
    Authors:
    Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
    Academic press:
    Information Processing Letters (rok: 2015, tom: 115 (5), strony: 527-531), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2015.01.001 - link to the publication
  6. Polynomial Kernelization for Removing Induced Claws and Diamonds
    Authors:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Academic press:
    Theory of Computing Systems (rok: 2016, tom: nie dotyczy, strony: 45313), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-016-9689-x - link to the publication
  1. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth
    Authors:
    Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Conference:
    Mathematical Foundations of Computer Science 2014 - 39th International Symposium, (MFCS 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 25-29.08.2014
    Status:
    Published
  2. Lower Bounds for Approximation Schemes for Closest String
    Authors:
    Marek Cygan, Daniel Loskhtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Conference:
    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:
    Published
    DOI:
    link to the publication
  3. Approximation and Kernelization for Chordal Vertex Deletion
    Authors:
    Bart Jansen, Marcin Pilipczuk
    Conference:
    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:
    Published
  4. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
    Authors:
    Hans Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Conference:
    40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 8-12.07.2013
    Status:
    Published
    DOI:
    link to the publication
  5. Fast hamiltonicity checking via bases of perfect matchings
    Authors:
    Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Conference:
    45th ACM Symposium on Theory of Computing (STOC 2013) (rok: 2013, ), Wydawca: ACM
    Data:
    konferencja 1-4.06.2013
    Status:
    Published
    DOI:
    link to the publication
  6. Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
    Authors:
    Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach, Michal Pilipczuk
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 1,2016
    Status:
    Published
  7. Polynomial Kernelization for Removing Induced Claws and Diamonds
    Authors:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Conference:
    Graph-Theoretic Concepts in Computer Science - 41st International Workshop (WG 2015) (rok: 2015, ), Wydawca: Springer (LNCS)
    Data:
    konferencja 17-19.06.2015
    Status:
    Published
  1. monografia naukowa
    Authors:
    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
    Book:
    Parameterized Algorithms (rok: 2015, tom: 1, strony: 3-555), Wydawca: Springer
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy