Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Uogólnienia problemów rozpoznawania w klasach grafów reprezentowanych geometrycznie i za pomocą porządków

2015/17/B/ST6/01873

Słowa kluczowe:

rozpoznawanie grafów rozszerzanie częściowych reprezentacji modyfikacje grafów geometryczne grafy przecięć

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_15: Matematyczne aspekty informatyki

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 Tomasz Krawczyk 

Liczba wykonawców projektu: 3

Konkurs: OPUS 9 - ogłoszony 2015-03-16

Przyznana kwota: 189 600 PLN

Rozpoczęcie projektu: 2016-02-01

Zakończenie projektu: 2019-07-31

Planowany czas trwania projektu: 24 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.

Dane z raportu końcowego

  • Publikacje w czasopismach (5)
  • Teksty w publikacjach pokonferencyjnych (4)
  1. On-line partitioning of width w posets into w^O(\log \log w) chains IF: 0,911
    Autorzy:
    Bartłomiej Bosek, Tomasz Krawczyk
    Czasopismo:
    European Journal of Combinatorics (rok: 2020, ), Wydawca: Elsevier Science BV
    Status:
    Przyjęta do publikacji
    Doi:
    10.1016/j.ejc.2020.103202 - link do publikacji
  2. Defective 3-Paintability of Planar Graphs IF: 0,759
    Autorzy:
    Grzegorz Gutowski, Ming Han, Tomasz Krawczyk, Xuding Zhu
    Czasopismo:
    The Electronic Journal of Combinatorics (rok: 2018, tom: 25 (2), strony: P2.34 (20 stron)), Wydawca: ELECTRONIC JOURNAL OF COMBINATORICS
    Status:
    Opublikowana
  3. Testing isomorphism of circular-arc graphs in linear time -- Hsu's approach revisited IF: 1,703
    Autorzy:
    Tomasz Krawczyk
    Czasopismo:
    SIAM Journal on Computing (SICOMP) , Wydawca: SIAM PUBLICATIONS
    Status:
    Złożona
  4. The Partial Visibility Representation Extension Problem IF: 0,843
    Autorzy:
    Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta
    Czasopismo:
    ALGORITHMICA (rok: 2018, tom: 80 (8), strony: 2286-2323), Wydawca: SPRINGER
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-017-0322-4 - link do publikacji
  5. The Slow-coloring Game on Sparse Graphs: k-Degenerate, Planar, and Outerplanar
    Autorzy:
    Grzegorz Gutowski, Tomasz Krawczyk, Krzysztof Maziarz, Douglas B. West, Michał Zając, Xuding Zhu
    Czasopismo:
    Journal of Combinatorics , Wydawca: INT PRESS BOSTON
    Status:
    Przyjęta do publikacji
  1. Extending Partial Representations of Trapezoid Graphs
    Autorzy:
    Tomasz Krawczyk, Bartosz Walczak
    Konferencja:
    43rd International Workshop on Graph-Theoretic Concepts in Computer Science (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 21-23 czerwca
    Status:
    Opublikowana
  2. Subexponential-time algorithms for finding large induced sparse subgraphs
    Autorzy:
    Jana Novotna, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Konferencja:
    14th International Symposium on Parameterized and Exact Computation (IPEC 2019) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 11-13 wrzesień
    Status:
    Opublikowana
  3. Vertex deletion into bipartite permutation graphs
    Autorzy:
    Łukasz Bozyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotna, Karolina Okrasa
    Konferencja:
    IPEC 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 14-18 grudnia, 2020
    Status:
    Przyjęta do publikacji
  4. The Partial Visibility Representation Extension Problem
    Autorzy:
    Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta
    Konferencja:
    24th International Symposium on Graph Drawing & Network Visualization, GD 2016 (rok: 2016, ), Wydawca: Springer, Lecture Notes in Theoretical Computer Science
    Data:
    konferencja 19-21 wrzesień
    Status:
    Opublikowana