Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Losowe zachłanne algorytmy kolorowania hipergrafów.

2016/21/B/ST6/02165

Słowa kluczowe:

kolorowanie hipergrafów algorytmy zachłanne własność B

Deskryptory:

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

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Jakub Kozik 

Liczba wykonawców projektu: 7

Konkurs: OPUS 11 - ogłoszony 2016-03-15

Przyznana kwota: 469 370 PLN

Rozpoczęcie projektu: 2017-02-03

Zakończenie projektu: 2021-10-02

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

Status projektu: Projekt rozliczony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Zakupiona aparatura

  1. laptop. Za kwotę 8 000 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (4)
  • Teksty w publikacjach pokonferencyjnych (6)
  1. The Slow-coloring Game on Sparse Graphs: k-Degenerate, Planar, and Outerplanar
    Autorzy:
    Grzegorz Gutowski, Tomasz Krawczyk, Douglas B. West, Michał Zając, Xuding Zhu
    Czasopismo:
    Journal of Combinatorics (rok: 2021, tom: 12, strony: 283 – 302), Wydawca: International Press of Boston, Inc.
    Status:
    Opublikowana
    Doi:
    10.4310/JOC.2021.v12.n2.a6 - link do publikacji
  2. PLANE GRAPHS ARE FACIALLY-NON-REPETITIVELY 10^(4*10^7) -CHOOSABLE
    Autorzy:
    GRZEGORZ GUTOWSKI
    Czasopismo:
    Electronic Journal of Combinatorics (rok: 2018, tom: 25 (1), strony: (13 stron)), Wydawca: Electronic Journal of Combinatorics
    Status:
    Opublikowana
    Doi:
    brak - link do publikacji
  3. Random hypergraphs and Property B
    Autorzy:
    Lech Duraj, Jakub Kozik, Dmitry Shabanov
    Czasopismo:
    European Journal of Combinatorics (rok: 2021, tom: 91, strony: 45302), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ejc.2020.103205 - link do publikacji
  4. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Autorzy:
    Lech Duraj, Marvin Künnemann, Adam Polak
    Czasopismo:
    Algorithmica (rok: 2019, tom: 81, strony: 3968–3992), Wydawca: Springer US
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-018-0485-7 - link do publikacji
  1. A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS
    Autorzy:
    LECH DURAJ, GRZEGORZ GUTOWSKI, JAKUB KOZIK
    Konferencja:
    The 45th International Colloquium on Automata, Languages, and Programming (ICALP) (rok: 2018, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 09-13 lipca 2018
    Status:
    Opublikowana
  2. Improving Gebauer's construction of 3-chromatic hypergraphs with few edges
    Autorzy:
    Jakub Kozik
    Konferencja:
    International Colloquium on Automata Languages and Programming [ICALP 2021] (rok: 2021, ), Wydawca: Leibniz International Proceedings in Informatics (LIPIcs)
    Data:
    konferencja 12–16 lipca 2021
    Status:
    Opublikowana
  3. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem
    Autorzy:
    Lech Duraj
    Konferencja:
    The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 2020-03-10-13
    Status:
    Opublikowana
  4. Equivalences between triangle and range query problems
    Autorzy:
    Lech Duraj,Krzysztof Kleiner,Adam Polak,Virginia Vassilevska Williams
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA'20) (rok: 2020, ), Wydawca: Society for Industrial and Applied Mathematics
    Data:
    konferencja 2020-01-05-08
    Status:
    Opublikowana
    Doi:
    link do publikacji
  5. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Autorzy:
    Lech Duraj, Marvin Künnemann, Adam Polak
    Konferencja:
    12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 04-08 września 2017
    Status:
    Opublikowana
  6. Online Coloring of Short Intervals
    Autorzy:
    Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos and Adam Polak
    Konferencja:
    International Conference on Approximation Algorithms for Combinatorial Optimization Problems (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 17-19 sierpnia 2020
    Status:
    Opublikowana
    Doi:
    link do publikacji

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy