Zmiana języka

Projects search

Random greedy algorithms for hypergraph coloring.

2016/21/B/ST6/02165

Keywords

Descriptors

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

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

Voivodeship: 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
2017-02-03
Project end date
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. Cost: 8 000 PLN

Information in the final report

Publication in academic press/journals (4)

  1. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

    Authors:
    Lech Duraj, Marvin Künnemann, Adam Polak
    Academic press:
    Algorithmica (year: 2019, volume: 81, pages: 3968–3992), Publisher: Springer US
    Status:
    Published
    DOI:
    10.1007/s00453-018-0485-7 – link to the publication

  2. Random hypergraphs and Property B

    Authors:
    Lech Duraj, Jakub Kozik, Dmitry Shabanov
    Academic press:
    European Journal of Combinatorics (year: 2021, volume: 91, pages: 46033), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2020.103205 – link to the publication

  3. 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 (year: 2021, volume: 12, pages: 283 – 302), Publisher: International Press of Boston, Inc.
    Status:
    Published
    DOI:
    10.4310/JOC.2021.v12.n2.a6 – link to the publication

  4. PLANE GRAPHS ARE FACIALLY-NON-REPETITIVELY 10^(4*10^7) -CHOOSABLE

    Authors:
    GRZEGORZ GUTOWSKI
    Academic press:
    Electronic Journal of Combinatorics (year: 2018, volume: 25 (1), pages: (13 stron)), Publisher: Electronic Journal of Combinatorics
    Status:
    Published
    DOI:
    link to the publication

Articles in post-conference publications (6)

  1. 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) (year: 2017, pages: 15:1–15:13), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Date:
    conference 04-08 września 2017
    Status:
    Published

  2. 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) (year: 2020, pages: 30-47), Publisher: Society for Industrial and Applied Mathematics
    Date:
    conference 2020-01-05-08
    Status:
    Published
    DOI:
    link to the publication

  3. Improving Gebauer's construction of 3-chromatic hypergraphs with few edges

    Authors:
    Jakub Kozik
    Conference:
    International Colloquium on Automata Languages and Programming [ICALP 2021] (year: 2021, pages: 89:1--89:9), Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
    Date:
    conference 12–16 lipca 2021
    Status:
    Published

  4. 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) (year: 2018, pages: 46:1-13), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Date:
    conference 09-13 lipca 2018
    Status:
    Published

  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) (year: 2020, pages: 41:1–41:18), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 2020-03-10-13
    Status:
    Published

  6. 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 (year: 2020, pages: 52:1-18), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 17-19 sierpnia 2020
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski