Lazy Queue Layouts of Posets
CC BY
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Sách |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Springer
2023
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s00453-022-01067-y https://dlib.phenikaa-uni.edu.vn/handle/PNK/8282 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| id |
oai:localhost:PNK-8282 |
|---|---|
| record_format |
dspace |
| spelling |
oai:localhost:PNK-82822023-04-25T06:55:34Z Lazy Queue Layouts of Posets Jawaherul Md., Alam Michael A., Bekos Martin, Gronemann Lazy Queue Layouts of Posets CC BY We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width w=2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width w>2. Our analysis implies an upper bound of (w−1)2+1 on the queue number of width-w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least w+1 queues in every linear extension, thereby disproving the conjecture for posets of width w>2 . 2023-04-25T06:55:34Z 2023-04-25T06:55:34Z 2022 Book https://link.springer.com/article/10.1007/s00453-022-01067-y https://dlib.phenikaa-uni.edu.vn/handle/PNK/8282 en application/pdf Springer |
| institution |
Digital Phenikaa |
| collection |
Digital Phenikaa |
| language |
English |
| topic |
Lazy Queue Layouts of Posets |
| spellingShingle |
Lazy Queue Layouts of Posets Jawaherul Md., Alam Michael A., Bekos Martin, Gronemann Lazy Queue Layouts of Posets |
| description |
CC BY |
| format |
Book |
| author |
Jawaherul Md., Alam Michael A., Bekos Martin, Gronemann |
| author_facet |
Jawaherul Md., Alam Michael A., Bekos Martin, Gronemann |
| author_sort |
Jawaherul Md., Alam |
| title |
Lazy Queue Layouts of Posets |
| title_short |
Lazy Queue Layouts of Posets |
| title_full |
Lazy Queue Layouts of Posets |
| title_fullStr |
Lazy Queue Layouts of Posets |
| title_full_unstemmed |
Lazy Queue Layouts of Posets |
| title_sort |
lazy queue layouts of posets |
| publisher |
Springer |
| publishDate |
2023 |
| url |
https://link.springer.com/article/10.1007/s00453-022-01067-y https://dlib.phenikaa-uni.edu.vn/handle/PNK/8282 |
| _version_ |
1764177437757800448 |
| score |
8.881002 |