Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Wymiar i reprezentacje częściowych porządków: złożoność obliczeniowa, ograniczenia i strukturalne własności

2015/18/E/ST6/00299

Słowa kluczowe:

częściowe porządki wymiar rzadkie klasy grafów

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • 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 Piotr Micek 

Liczba wykonawców projektu: 4

Konkurs: SONATA BIS 5 - ogłoszony 2015-06-15

Przyznana kwota: 537 600 PLN

Rozpoczęcie projektu: 2016-04-12

Zakończenie projektu: 2020-10-11

Planowany czas trwania projektu: 54 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/rocznego

  • Publikacje w czasopismach (12)
  • Teksty w publikacjach pokonferencyjnych (4)
  1. Boolean dimension and tree-width
    Autorzy:
    Stefan Felsner, Tamás Mészáros, Piotr Micek
    Czasopismo:
    Combinatorica (rok: 2020, tom: 40, strony: 655–677), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-020-4000-9 - link do publikacji
  2. Nowhere dense graph classes and dimension
    Autorzy:
    Gwenaël Joret, Patrice Ossona de Mendez, Piotr Micek, Veit Wiechert
    Czasopismo:
    Combinatorica (rok: 2019, tom: 39, strony: 1055-1079), Wydawca: Springer Heidelberg
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-019-3892-8 - link do publikacji
  3. On an Extremal Problem for Poset Dimension
    Autorzy:
    Grzegorz Guśpiel, Piotr Micek, Adam Polak
    Czasopismo:
    Order (rok: 2018, tom: 35, strony: 489-493), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s11083-017-9444-1 - link do publikacji
  4. A note on the minimum number of edges in hypergraphs with property O
    Autorzy:
    Gal Kronenberg, Christopher Kusch, Ander Lamaison, Piotr Micek, Tuan Tran
    Czasopismo:
    European Journal of Combinatorics (rok: 2019, tom: 81, strony: 172--177), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ejc.2019.05.002 - link do publikacji
  5. Burling Graphs, Chromatic Number, and Orthogonal Tree-Decompositions
    Autorzy:
    Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert
    Czasopismo:
    Electronic Journal of Combinatorics (rok: 2018, tom: 25 (1), strony: -), Wydawca: Electronic Journal of Combinatorics
    Status:
    Opublikowana
    Doi:
    10.37236/7052 - link do publikacji
  6. Planar Posets Have Dimension at Most Linear in Their Height
    Autorzy:
    Gwenaël Joret, Piotr Micek, Veit Wiechert
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2017, tom: 31 (4), strony: 2754--2790), Wydawca: SIAM PUBLICATIONS
    Status:
    Opublikowana
    Doi:
    10.1137/17M111300X - link do publikacji
  7. Seymour's conjecture on 2-connected graphs of large pathwidth
    Autorzy:
    Tony Huynh, Gwenaël Joret, Piotr Micek, David Wood
    Czasopismo:
    Combinatorica (rok: 2020, tom: 40, strony: 839-868), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-020-3941-3 - link do publikacji
  8. The dimension of posets with planar cover graphs excluding two long incomparable chains
    Autorzy:
    David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
    Czasopismo:
    Journal of Combinatorial Theory, Series A (rok: 2019, tom: 164, strony: 45314), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.jcta.2018.11.016 - link do publikacji
  9. Boolean Dimension, Components and Blocks
    Autorzy:
    Tamás Mészáros, Piotr Micek, William T. Trotter
    Czasopismo:
    Order (rok: 2020, tom: 37, strony: 287-298), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s11083-019-09505-3 - link do publikacji
  10. Planar Graphs Have Bounded Queue-Number
    Autorzy:
    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood
    Czasopismo:
    Journal of the ACM (rok: 2020, tom: 67, strony: 38), Wydawca: Association for Computing Machinery
    Status:
    Opublikowana
    Doi:
    10.1145/3385731 - link do publikacji
  11. Sparsity and dimension
    Autorzy:
    Gwenaël Joret, Piotr Micek, Veit Wiechert
    Czasopismo:
    Combinatorica (rok: 2018, tom: 38/5, strony: 1129-1148), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-017-3638-4 - link do publikacji
  12. Excluding a ladder
    Autorzy:
    Tony Huynh, Gwenaël Joret, Piotr Micek, Michał T. Seweryn, Paul Wollan
    Czasopismo:
    Combinatorica , Wydawca: Springer Heidelberg
    Status:
    Przyjęta do publikacji
    Doi:
    brak - link do publikacji
  1. Planar Graphs have Bounded Queue-Number
    Autorzy:
    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood
    Konferencja:
    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (rok: 2019, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 43778
    Status:
    Opublikowana
  2. The queue-number of posets of bounded width or height
    Autorzy:
    Kolja Knauer, Piotr Micek, Torsten Ueckerdt
    Konferencja:
    26th International Symposium on Graph Drawing and Network Visualization (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 26.09.2018-28.09.2018
    Status:
    Opublikowana
  3. Boolean dimension and local dimension
    Autorzy:
    William T. Trotter, Bartosz Walczak
    Konferencja:
    The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17) (rok: 2017, ), Wydawca: Elsevier
    Data:
    konferencja 28.08.2017-1.09.2017
    Status:
    Opublikowana
  4. Burling graphs, chromatic number, and orthogonal tree-decompositions
    Autorzy:
    Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert
    Konferencja:
    The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17) (rok: 2017, ), Wydawca: Elsevier
    Data:
    konferencja 28.08.2017-1.09.2017
    Status:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy