Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Efficient planar graph algorithms

2014/13/B/ST6/01811

Keywords:

planar graph flows distance oracles matchings

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 hab. Piotr Sankowski 

Number of co-investigators in the project: 5

Call: OPUS 7 - announced on 2014-03-17

Amount awarded: 501 723 PLN

Project start date (Y-m-d): 2015-02-09

Project end date (Y-m-d): 2019-02-08

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

Project status: Project settled

Equipment purchased [PL]

  1. Komputer typu laptop z wyposażeniem oraz 3 letnią rozszerzoną gwarancją (3 szt.) (18 000 PLN)

Information in the final report

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (11)
  1. Optimal Decremental Connectivity in Planar Graphs
    Authors:
    Jakub Łącki, Piotr Sankowski
    Academic press:
    Theory of Computing Systems (rok: 2017, tom: 2,54444444444444, strony: 1037–1053), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-016-9709-x - link to the publication
  1. Contracting a Planar Graph Efficiently
    Authors:
    Jacob Holm and Giuseppe F. Italiano and Adam Karczmarz and Jakub Lacki and Eva Rotenberg and Piotr Sankowski
    Conference:
    25th Annual European Symposium on Algorithms (ESA 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 2017
    Status:
    Published
    DOI:
    link to the publication
  2. Decrementai Transitive Closure and Shortest Paths for Planar Digraphs and Beyond Read More: https://epubs.siam.org/doi/10.1137/1.9781611975031.5
    Authors:
    Adam Karczmarz
    Conference:
    Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (rok: 2018, ), Wydawca: SIAM
    Data:
    konferencja 2018
    Status:
    Published
    DOI:
    link to the publication
  3. Improved Bounds for Shortest Paths in Dense Distance Graphs
    Authors:
    Pawel Gawrychowski and Adam Karczmarz
    Conference:
    45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (rok: 2018, ), Wydawca: LIPIcs
    Data:
    konferencja 2018
    Status:
    Published
    DOI:
    link to the publication
  4. Decremental SPQR-trees for Planar Graphs
    Authors:
    Jacob Holm and Giuseppe F. Italiano and Adam Karczmarz and Jakub Lacki and Eva Rotenberg
    Conference:
    26th Annual European Symposium on Algorithms (ESA 2018) (rok: 2018, ), Wydawca: LIPIcs
    Data:
    konferencja 2018
    Status:
    Published
    DOI:
    link to the publication
  5. Improved Distance Queries and Cycle Counting by Frobenius Normal Form
    Authors:
    Piotr Sankowski, Karol Węgrzycki
    Conference:
    34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 2017
    Status:
    Published
    DOI:
    link to the publication
  6. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
    Authors:
    Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych
    Conference:
    the Forty-Seventh Annual ACM on Symposium on Theory of Computing (rok: 2015, ), Wydawca: ACM
    Data:
    konferencja 15.06.2015-17.06.2015
    Status:
    Published
    DOI:
    link to the publication
  7. Decremental Single-Source Reachability in Planar Digraphs
    Authors:
    Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Piotr Sankowski
    Conference:
    49th Annual ACM Symposium on the Theory of Computing (rok: 2017, ), Wydawca: ACM
    Data:
    konferencja June 19-23
    Status:
    Accepted for publication
  8. A Simple Mergeable Dictionary
    Authors:
    Adam Karczmarz
    Conference:
    15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) (rok: 2016, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja June 22-24
    Status:
    Published
    DOI:
    link to the publication
  9. Fast and Simple Connectivity in Graph Timelines
    Authors:
    Adam Karczmarz, Jakub Łącki
    Conference:
    14th International Symposium Algorithms and Data Structures (WADS 2015) (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja August 5-7
    Status:
    Published
    DOI:
    link to the publication
  10. NC Algorithms for Weighted Planar Perfect Matching and Related Problems
    Authors:
    Piotr Sankowski
    Conference:
    45th International Colloquium on Automata, Languages, and Programming (rok: 2018, ), Wydawca: LIPIcs
    Data:
    konferencja 9.07.2018
    Status:
    Published
    DOI:
    link to the publication
  11. Why Do Cascade Sizes Follow a Power-Law?
    Authors:
    Karol Węgrzycki, Piotr Sankowski, Andrzej Pacuk, Piotr Wygocki
    Conference:
    26th International Conference on World Wide Web (rok: 2017, ), Wydawca: ACM
    Data:
    konferencja 03-07 kwietnia 2017
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy