Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Dynamic algorithms for directed graphs under weak assumptions about the adversary.

2018/29/N/ST6/00757

Keywords:

dynamic graph algorithms directed graphs reachability shortest paths

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 Adam Karczmarz 

Number of co-investigators in the project: 2

Call: PRELUDIUM 15 - announced on 2018-03-15

Amount awarded: 103 200 PLN

Project start date (Y-m-d): 2019-01-24

Project end date (Y-m-d): 2021-01-23

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

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

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

Information in the final report

  • Articles in post-conference publications (5)
  1. A Deterministic Parallel APSP Algorithm and its Applications
    Authors:
    Adam Karczmarz, Piotr Sankowski
    Conference:
    2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 10-13 stycznia 2021
    Status:
    Published
    DOI:
    link to the publication
  2. Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs
    Authors:
    Adam Karczmarz, Jakub Łącki
    Conference:
    3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020 (rok: 2020, ), Wydawca: SIAM
    Data:
    konferencja 6-7 stycznia 2020
    Status:
    Published
    DOI:
    link to the publication
  3. Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs
    Authors:
    Panagiotis Charalampopoulos, Adam Karczmarz
    Conference:
    28th Annual European Symposium on Algorithms, ESA 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9 września 2020
    Status:
    Published
    DOI:
    link to the publication
  4. Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
    Authors:
    Adam Karczmarz, Jakub Łącki
    Conference:
    27th Annual European Symposium on Algorithms, ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11 września 2019
    Status:
    Published
    DOI:
    link to the publication
  5. Min-Cost Flow in Unit-Capacity Planar Graphs
    Authors:
    Adam Karczmarz, Piotr Sankowski
    Conference:
    27th Annual European Symposium on Algorithms, ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11 września 2019
    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