Staff View: Lazy Queue Layouts of Posets

Lazy Queue Layouts of Posets

CC BY

Saved in:

Bibliographic Details
Main Authors:	Jawaherul Md., Alam, Michael A., Bekos, Martin, Gronemann
Format:	Book
Language:	English
Published:	Springer 2023
Subjects:	Lazy Queue Layouts of Posets
Online Access:	https://link.springer.com/article/10.1007/s00453-022-01067-y https://dlib.phenikaa-uni.edu.vn/handle/PNK/8282
Tags:	Add Tag No Tags, Be the first to tag this record!

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.891145

Lazy Queue Layouts of Posets

Similar Items