Zmiana języka

Projects search

Parameterized algorithms in graph problems and permutation pattern matching.

2012/05/D/ST6/03214

Keywords

Descriptors

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

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

Voivodeship: mazowieckie

Other projects carried out by the institution »

Principal investigator (from the host institution)

dr Marek Adam 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
2013-02-04
Project end date
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.. Cost: 6 000 PLN
  2. Komputer stacjonarny. Cost: 4 000 PLN

Information in the final report

Publication in academic press/journals (6)

  1. 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 (year: 2016, volume: nie dotyczy, pages: 46044), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-016-9689-x – link to the publication

  2. Faster deterministic Feedback Vertex Set

    Authors:
    Tomasz Kociumaka, Marcin Pilipczuk
    Academic press:
    Information Processing Letters (year: 2014, volume: 114 (10), pages: 556-560), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2014.05.001 – link to the publication

  3. Kernelization lower bound for Permutation Pattern Matching

    Authors:
    Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
    Academic press:
    Information Processing Letters (year: 2015, volume: 115 (5), pages: 527-531), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2015.01.001 – link to the publication

  4. Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth

    Authors:
    Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Status:
    Accepted for publication

  5. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

    Authors:
    Hans Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
    Status:
    Accepted for publication

  6. A tight lower bound for Vertex Planarization on graphs of bounded treewidth

    Authors:
    Marcin Pilipczuk
    Status:
    Accepted for publication

Articles in post-conference publications (7)

  1. 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) (year: 2013, pages: 196-207), Publisher: Springer
    Date:
    conference 8-12.07.2013
    Status:
    Published
    DOI:
    link to the publication

  2. 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) (year: 2013, pages: 301-310), Publisher: ACM
    Date:
    conference 1-4.06.2013
    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) (year: 2017, pages: 1399-1418), Publisher: SIAM
    Date:
    conference 16-19.01.2017
    Status:
    Published

  4. 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). (year: 2016, pages: 12:1-12:10), Publisher: LIPIcs: Leibniz International |Proceedings in Informatics
    Date:
    conference 22-24.06.2016
    Status:
    Published

  5. 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) (year: 2014, pages: 189-200), Publisher: Springer
    Date:
    conference 25-29.08.2014
    Status:
    Published

  6. 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) (year: 2015, pages: 440-455), Publisher: Springer (LNCS)
    Date:
    conference 17-19.06.2015
    Status:
    Published

  7. 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) (year: 2016, pages: 1132-1151), Publisher: SIAM
    Date:
    conference 1,2016
    Status:
    Published

Book publications / chapters in book publications (1)

  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 (year: 2015, volume: 1, pages: 3-555), Publisher: Springer
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski