Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Generalizations of recognition problems in classes of graphs with geometric and order representations

2015/17/B/ST6/01873

Keywords:

graph recognition partial representation extension graph modifications geometric intersection graphs

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_15: Mathematical aspects of computer science

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

Number of co-investigators in the project: 3

Call: OPUS 9 - announced on 2015-03-16

Amount awarded: 189 600 PLN

Project start date (Y-m-d): 2016-02-01

Project end date (Y-m-d): 2019-07-31

Project duration:: 42 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.

Information in the final report

  • Publication in academic press/journals (5)
  • Articles in post-conference publications (4)
  1. The Partial Visibility Representation Extension Problem
    Authors:
    Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta
    Academic press:
    ALGORITHMICA (rok: 2018, tom: 80 (8), strony: 2286-2323), Wydawca: SPRINGER
    Status:
    Published
    DOI:
    10.1007/s00453-017-0322-4 - link to the publication
  2. On-line partitioning of width w posets into w^O(\log \log w) chains
    Authors:
    Bartłomiej Bosek, Tomasz Krawczyk
    Academic press:
    European Journal of Combinatorics (rok: 2020, ), Wydawca: Elsevier Science BV
    Status:
    Accepted for publication
    DOI:
    10.1016/j.ejc.2020.103202 - link to the publication
  3. Testing isomorphism of circular-arc graphs in linear time -- Hsu's approach revisited
    Authors:
    Tomasz Krawczyk
    Academic press:
    SIAM Journal on Computing (SICOMP) , Wydawca: SIAM PUBLICATIONS
    Status:
    Submitted
    DOI:
    brak - link to the publication
  4. The Slow-coloring Game on Sparse Graphs: k-Degenerate, Planar, and Outerplanar
    Authors:
    Grzegorz Gutowski, Tomasz Krawczyk, Krzysztof Maziarz, Douglas B. West, Michał Zając, Xuding Zhu
    Academic press:
    Journal of Combinatorics , Wydawca: INT PRESS BOSTON
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  5. Defective 3-Paintability of Planar Graphs
    Authors:
    Grzegorz Gutowski, Ming Han, Tomasz Krawczyk, Xuding Zhu
    Academic press:
    The Electronic Journal of Combinatorics (rok: 2018, tom: 25 (2), strony: P2.34 (20 stron)), Wydawca: ELECTRONIC JOURNAL OF COMBINATORICS
    Status:
    Published
    DOI:
    brak - link to the publication
  1. Subexponential-time algorithms for finding large induced sparse subgraphs
    Authors:
    Jana Novotna, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Conference:
    14th International Symposium on Parameterized and Exact Computation (IPEC 2019) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 11-13 wrzesień
    Status:
    Published
  2. Extending Partial Representations of Trapezoid Graphs
    Authors:
    Tomasz Krawczyk, Bartosz Walczak
    Conference:
    43rd International Workshop on Graph-Theoretic Concepts in Computer Science (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 21-23 czerwca
    Status:
    Published
  3. Vertex deletion into bipartite permutation graphs
    Authors:
    Łukasz Bozyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotna, Karolina Okrasa
    Conference:
    IPEC 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 14-18 grudnia, 2020
    Status:
    Accepted for publication
  4. The Partial Visibility Representation Extension Problem
    Authors:
    Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta
    Conference:
    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:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy