Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Random greedy algorithms for hypergraph coloring.

2016/21/B/ST6/02165

Keywords:

hypergraph coloring greedy algorithm property B

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_14: Discrete mathematics and combinatorics

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Jakub Kozik 

Number of co-investigators in the project: 7

Call: OPUS 11 - announced on 2016-03-15

Amount awarded: 469 370 PLN

Project start date (Y-m-d): 2017-02-03

Project end date (Y-m-d): 2021-10-02

Project duration:: 56 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. laptop (8 000 PLN)

Information in the final report

  • Publication in academic press/journals (4)
  • Articles in post-conference publications (6)
  1. Random hypergraphs and Property B
    Authors:
    Lech Duraj, Jakub Kozik, Dmitry Shabanov
    Academic press:
    European Journal of Combinatorics (rok: 2021, tom: 91, strony: 45302), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2020.103205 - link to the publication
  2. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Authors:
    Lech Duraj, Marvin Künnemann, Adam Polak
    Academic press:
    Algorithmica (rok: 2019, tom: 81, strony: 3968–3992), Wydawca: Springer US
    Status:
    Published
    DOI:
    10.1007/s00453-018-0485-7 - link to the publication
  3. PLANE GRAPHS ARE FACIALLY-NON-REPETITIVELY 10^(4*10^7) -CHOOSABLE
    Authors:
    GRZEGORZ GUTOWSKI
    Academic press:
    Electronic Journal of Combinatorics (rok: 2018, tom: 25 (1), strony: (13 stron)), Wydawca: Electronic Journal of Combinatorics
    Status:
    Published
    DOI:
    brak - link to the publication
  4. The Slow-coloring Game on Sparse Graphs: k-Degenerate, Planar, and Outerplanar
    Authors:
    Grzegorz Gutowski, Tomasz Krawczyk, Douglas B. West, Michał Zając, Xuding Zhu
    Academic press:
    Journal of Combinatorics (rok: 2021, tom: 12, strony: 283 – 302), Wydawca: International Press of Boston, Inc.
    Status:
    Published
    DOI:
    10.4310/JOC.2021.v12.n2.a6 - link to the publication
  1. A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS
    Authors:
    LECH DURAJ, GRZEGORZ GUTOWSKI, JAKUB KOZIK
    Conference:
    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:
    Published
  2. Improving Gebauer's construction of 3-chromatic hypergraphs with few edges
    Authors:
    Jakub Kozik
    Conference:
    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:
    Published
  3. Online Coloring of Short Intervals
    Authors:
    Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos and Adam Polak
    Conference:
    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:
    Published
    DOI:
    link to the publication
  4. Equivalences between triangle and range query problems
    Authors:
    Lech Duraj,Krzysztof Kleiner,Adam Polak,Virginia Vassilevska Williams
    Conference:
    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:
    Published
    DOI:
    link to the publication
  5. A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem
    Authors:
    Lech Duraj
    Conference:
    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:
    Published
  6. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
    Authors:
    Lech Duraj, Marvin Künnemann, Adam Polak
    Conference:
    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:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy