Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Rozgrywane kolorowanie grafów i zbiorów częściowo uporządkowanych

2011/03/B/ST6/01367

Słowa kluczowe:

częściowy porządek algorytm on-line kolorowanie First-Fit graf porównywalności twierdzenie Dilwortha twierdzenie Ramseya

Deskryptory:

  • ST6_7: Teoretyczne podstawy informatyki, w tym informatyka kwantowa
  • ST1_15: Matematyczne aspekty informatyki
  • 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):

prof. Jarosław Grytczuk 

Liczba wykonawców projektu: 5

Konkurs: OPUS 2 - ogłoszony 2011-09-15

Przyznana kwota: 585 000 PLN

Rozpoczęcie projektu: 2012-08-28

Zakończenie projektu: 2015-05-27

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

Status projektu: Projekt rozliczony

Dane z raportu końcowego

  • Publikacje w czasopismach (8)
  • Teksty w publikacjach pokonferencyjnych (2)
  1. Additive coloring of planar graphs IF: 0,37
    Autorzy:
    Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki, Wiktor Żelazny
    Czasopismo:
    Graphs and Combinatorics (rok: 2014, tom: 30, strony: 1087-1098), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00373-013-1331-y - link do publikacji
  2. Fractional and j-fold colouring of the plane IF: 0,692
    Autorzy:
    Jarosław Grytczuk, Konstanty Junosza-Szaniawski, Joanna Sokół, Krzysztof Węsek
    Czasopismo:
    Discrete and Computational Geometry (rok: 2016, tom: 55, strony: 594–609), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00454-016-9769-3 - link do publikacji
  3. Triangle-free geometric intersection graphs with no large independent sets IF: 0,723
    Autorzy:
    Bartosz Walczak
    Czasopismo:
    Discrete and Computational Geometry (rok: 2015, tom: 53, strony: 221-225), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00454-014-9645-y - link do publikacji
  4. A lazy approach to on-line bipartite matching IF: 0,567
    Autorzy:
    Jakub Kozik, Grzegorz Matecki
    Czasopismo:
    Algorithmica (rok: 2016, ), Wydawca: Springer
    Status:
    Złożona
  5. An Improved Subexponential Bound for On-line Chain Partitioning IF: 0,775
    Autorzy:
    Bartłomiej Bosek, Hal A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, Matthew E. Smith
    Czasopismo:
    Journal of Combinatorial Theory, Series A (rok: 2015, tom: brak, strony: brak), Wydawca: Elsevier
    Status:
    Złożona
  6. How to play Thue games IF: 0,652
    Autorzy:
    Jarosław Grytczuk, Karol Kosiński, Michał Zmarz
    Czasopismo:
    Teoretical Computer Science (rok: 2015, tom: 582, strony: 2015), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2015.03.036 - link do publikacji
  7. On the Duality of Semiantichains and Unichain Coverings IF: 0,487
    Autorzy:
    Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki
    Czasopismo:
    Order (rok: 2016, tom: 33, strony: 29-38), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s11083-015-9348-x - link do publikacji
  8. On-line approach to off-line coloring problems on graphs with geometric representations IF: 0,783
    Autorzy:
    Tomasz Krawczyk, Bartosz Walczak
    Czasopismo:
    Combinatorica (rok: 2016, ), Wydawca: Springer
    Status:
    Przyjęta do publikacji
    Doi:
    10.1007/s00493-016-3414-x - link do publikacji
  1. Asymmetric coloring games on incomparability graphs
    Autorzy:
    Tomasz Krawczyk, Bartosz Walczak
    Konferencja:
    EuroComb 2015 (rok: 2015, ), Wydawca: Lecture Notes in Discrete Mathematics
    Data:
    konferencja 31.08.2015-4.09.2015
    Status:
    Opublikowana
  2. Coloring relatives of interval overlap graphs via on-line games
    Autorzy:
    Tomasz Krawczyk, Bartosz Walczak
    Konferencja:
    41International Colloquium on Automata, Languages, and Programming (ICALP 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 7-11.07.2014
    Status:
    Opublikowana