Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Efektywne algorytmy dla grafów planarnych

2014/13/B/ST6/01811

Słowa kluczowe:

grafy planarne przepływy wyrocznie odległości skojarzenia

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

Liczba wykonawców projektu: 5

Konkurs: OPUS 7 - ogłoszony 2014-03-17

Przyznana kwota: 501 723 PLN

Rozpoczęcie projektu: 2015-02-09

Zakończenie projektu: 2019-02-08

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

Status projektu: Projekt rozliczony

Zakupiona aparatura

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

Dane z raportu końcowego/rocznego

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