Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

On new techniques for matching and flow problems

2013/11/D/ST6/03100

Keywords:

algorithm graph matching flow online

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_1: Logic and foundations

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 Bartłomiej Bosek 

Number of co-investigators in the project: 4

Call: SONATA 6 - announced on 2013-09-16

Amount awarded: 515 700 PLN

Project start date (Y-m-d): 2014-07-29

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

Project duration:: 60 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. sprzęt komputerowy (10 000 PLN)

Information in the final report

  • Publication in academic press/journals (6)
  • Articles in post-conference publications (3)
  1. Majority Coloring Game
    Authors:
    Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak
    Academic press:
    Discrete Applied Mathematics (rok: 2019, tom: 255, strony: 15-20), Wydawca: Elsevier Science BV
    Status:
    Published
    DOI:
    10.1016/j.dam.2018.07.020 - link to the publication
  2. Local Dimension is Unbounded for Planar Posets
    Authors:
    Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter
    Academic press:
    Electronic Journal of Combinatorics (rok: 2020, ), Wydawca: Electronic Journal of Combinatorics
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  3. Shortest Augmenting Paths for Online Matchings on Trees
    Authors:
    Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych
    Academic press:
    Theory of Computing Systems (rok: 2018, tom: 62, strony: 337-348), Wydawca: Springer US
    Status:
    Published
    DOI:
    10.1007/s00224-017-9838-x - link to the publication
  4. 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: 2021, tom: 91, strony: 103202), Wydawca: Elsevier Science BV
    Status:
    Accepted for publication
    DOI:
    10.1016/j.ejc.2020.103202 - link to the publication
  5. Planar posets that are accessible from below have dimension at most 6
    Authors:
    Csaba Biró, Bartłomiej Bosek, Heather Christina Smith, William T. Trotter, Ruidong Wang, Stephen J. Young
    Academic press:
    Order (rok: 2020, ), Wydawca: Springer Netherlands
    Status:
    Accepted for publication
    DOI:
    10.1007/s11083-020-09525-4 - link to the publication
  6. Majority Choosability of Digraphs
    Authors:
    Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk
    Academic press:
    Electronic Journal of Combinatorics (rok: 2017, tom: 24 (3), strony: P3.57), Wydawca: Electronic Journal of Combinatorics
    Status:
    Published
    DOI:
    brak - link to the publication
  1. Shortest Augmenting Paths for Online Matchings on Trees
    Authors:
    Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych
    Conference:
    13th Workshop on Approximation and Online Algorithms (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 14-18.09.2015
    Status:
    Published
    DOI:
    link to the publication
  2. A Tight Bound for Shortest Augmenting Paths on Trees
    Authors:
    Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz
    Conference:
    Latin American Theoretical Informatics 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 16-19 kwietnia 2018
    Status:
    Published
    DOI:
    link to the publication
  3. Online bipartite matching in offline time
    Authors:
    Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych
    Conference:
    2014 IEEE Annual Symposium on Foundations of Computer Science (rok: 2014, ), Wydawca: IEEE Computer Soc.
    Data:
    konferencja 18-21.10.2014
    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