Geodesic
An easy subexponential bound for online chain partitioning
Bartłomiej Bosek1 ; H. A. Kierstead2 ; Tomasz Krawczyk1 ; Grzegorz Matecki1 ; Matthew E. Smith2
1Jagiellonian University in Kraków
2Arizona State University
The electronic journal of combinatorics, Tome 25 (2018) no. 2

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv
Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width $w$ into $w^{14\lg w}$ chains. We improve this to $w^{6.5 \lg w + 7}$ with a simpler and shorter proof by combining the work of Bosek & Krawczyk with work of Kierstead & Smith on First-Fit chain partitioning of ladder-free posets. We also provide examples illustrating the limits of our approach.
DOI : 10.37236/7231
Classification : 06A07, 05C15, 68W27
Mots-clés : partially ordered set, poset, first-fit, online chain partition, ladder, regular poset

Bartłomiej Bosek  1   ; H. A. Kierstead  2   ; Tomasz Krawczyk  1   ; Grzegorz Matecki  1   ; Matthew E. Smith  2

1 Jagiellonian University in Kraków
2 Arizona State University 
Bartłomiej Bosek; H. A. Kierstead; Tomasz Krawczyk; Grzegorz Matecki; Matthew E. Smith. An easy subexponential bound for online chain partitioning. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7231
@article{10_37236_7231,
     author = {Bart{\l}omiej Bosek and H. A. Kierstead and Tomasz Krawczyk and Grzegorz Matecki and Matthew E. Smith},
     title = {An easy subexponential bound for online chain partitioning},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7231},
     zbl = {1390.06001},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7231/}
}
TY  - JOUR
AU  - Bartłomiej Bosek
AU  - H. A. Kierstead
AU  - Tomasz Krawczyk
AU  - Grzegorz Matecki
AU  - Matthew E. Smith
TI  - An easy subexponential bound for online chain partitioning
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7231/
DO  - 10.37236/7231
ID  - 10_37236_7231
ER  - 
%0 Journal Article
%A Bartłomiej Bosek
%A H. A. Kierstead
%A Tomasz Krawczyk
%A Grzegorz Matecki
%A Matthew E. Smith
%T An easy subexponential bound for online chain partitioning
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7231/
%R 10.37236/7231
%F 10_37236_7231

Cité par Sources :