Lazy Queue Layouts of Posets Article Swipe

PDF

Jawaherul Md. Alam , Michael A. Bekos , Martin Gronemann , Michael Kaufmann , Sergey Pupyrev ·

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.1007/s00453-022-01067-y

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

Related Topics

Concepts

Algorithm Conjecture Computer science Mathematics Combinatorics

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1007/s00453-022-01067-y
PDF: https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf
OA Status: hybrid
Cited By: 2
References: 23
Related Works: 10
OpenAlex ID: https://openalex.org/W3080632939

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3080632939

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/s00453-022-01067-y

Digital Object Identifier
Title: Lazy Queue Layouts of Posets

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-11-28

Full publication date if available
Authors: Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev

List of authors in order
Landing page: https://doi.org/10.1007/s00453-022-01067-y

Publisher landing page
PDF URL: https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf

Direct OA link when available
Concepts: Algorithm, Conjecture, Computer science, Mathematics, Combinatorics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2023: 1, 2020: 1

Per-year citation counts (last 5 years)
References (count): 23

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3080632939
doi	https://doi.org/10.1007/s00453-022-01067-y
ids.doi	https://doi.org/10.1007/s00453-022-01067-y
ids.mag	3080632939
ids.openalex	https://openalex.org/W3080632939
fwci	0.26334776
type	article
title	Lazy Queue Layouts of Posets
biblio.issue	5
biblio.volume	85
biblio.last_page	1201
biblio.first_page	1176
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9994000196456909
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T11329
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.996999979019165
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2607
topics[1].subfield.display_name	Discrete Mathematics and Combinatorics
topics[1].display_name	Limits and Structures in Graph Theory
topics[2].id	https://openalex.org/T10948
topics[2].field.id	https://openalex.org/fields/26
topics[2].field.display_name	Mathematics
topics[2].score	0.9919999837875366
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2607
topics[2].subfield.display_name	Discrete Mathematics and Combinatorics
topics[2].display_name	Advanced Combinatorial Mathematics
funders[0].id	https://openalex.org/F4320331527
funders[0].ror	https://ror.org/01qg3j183
funders[0].display_name	University of Ioannina
is_xpac	False
apc_list.value	2290
apc_list.currency	EUR
apc_list.value_usd	2890
apc_paid.value	2290
apc_paid.currency	EUR
apc_paid.value_usd	2890
concepts[0].id	https://openalex.org/C11413529
concepts[0].level	1
concepts[0].score	0.6500206589698792
concepts[0].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[0].display_name	Algorithm
concepts[1].id	https://openalex.org/C2780990831
concepts[1].level	2
concepts[1].score	0.42758461833000183
concepts[1].wikidata	https://www.wikidata.org/wiki/Q319141
concepts[1].display_name	Conjecture
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.4229412376880646
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.2854252755641937
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.227818101644516
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
keywords[0].id	https://openalex.org/keywords/algorithm
keywords[0].score	0.6500206589698792
keywords[0].display_name	Algorithm
keywords[1].id	https://openalex.org/keywords/conjecture
keywords[1].score	0.42758461833000183
keywords[1].display_name	Conjecture
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.4229412376880646
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.2854252755641937
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.227818101644516
keywords[4].display_name	Combinatorics
language	en
locations[0].id	doi:10.1007/s00453-022-01067-y
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S89324355
locations[0].source.issn	0178-4617, 1432-0541
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	0178-4617
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Algorithmica
locations[0].source.host_organization	https://openalex.org/P4310319900
locations[0].source.host_organization_name	Springer Science+Business Media
locations[0].source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
locations[0].source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
locations[0].license	cc-by
locations[0].pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Algorithmica
locations[0].landing_page_url	https://doi.org/10.1007/s00453-022-01067-y
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5050501069
authorships[0].author.orcid
authorships[0].author.display_name	Jawaherul Md. Alam
authorships[0].affiliations[0].raw_affiliation_string	Amazon Inc., Tempe, AZ, USA
authorships[0].author_position	first
authorships[0].raw_author_name	Jawaherul Md. Alam
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Amazon Inc., Tempe, AZ, USA
authorships[1].author.id	https://openalex.org/A5006472576
authorships[1].author.orcid	https://orcid.org/0000-0002-3414-7444
authorships[1].author.display_name	Michael A. Bekos
authorships[1].countries	GR
authorships[1].affiliations[0].institution_ids	https://openalex.org/I194019607
authorships[1].affiliations[0].raw_affiliation_string	Department of Mathematics, University of Ioannina, Ioannina, Greece
authorships[1].institutions[0].id	https://openalex.org/I194019607
authorships[1].institutions[0].ror	https://ror.org/01qg3j183
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I194019607
authorships[1].institutions[0].country_code	GR
authorships[1].institutions[0].display_name	University of Ioannina
authorships[1].author_position	middle
authorships[1].raw_author_name	Michael A. Bekos
authorships[1].is_corresponding	True
authorships[1].raw_affiliation_strings	Department of Mathematics, University of Ioannina, Ioannina, Greece
authorships[2].author.id	https://openalex.org/A5080178526
authorships[2].author.orcid	https://orcid.org/0000-0003-2565-090X
authorships[2].author.display_name	Martin Gronemann
authorships[2].countries	AT
authorships[2].affiliations[0].institution_ids	https://openalex.org/I145847075
authorships[2].affiliations[0].raw_affiliation_string	Algorithms and Complexity Group, TU Wien, Vienna, Austria
authorships[2].institutions[0].id	https://openalex.org/I145847075
authorships[2].institutions[0].ror	https://ror.org/04d836q62
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I145847075
authorships[2].institutions[0].country_code	AT
authorships[2].institutions[0].display_name	TU Wien
authorships[2].author_position	middle
authorships[2].raw_author_name	Martin Gronemann
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Algorithms and Complexity Group, TU Wien, Vienna, Austria
authorships[3].author.id	https://openalex.org/A5103045561
authorships[3].author.orcid	https://orcid.org/0000-0001-9186-3538
authorships[3].author.display_name	Michael Kaufmann
authorships[3].countries	DE
authorships[3].affiliations[0].institution_ids	https://openalex.org/I8087733
authorships[3].affiliations[0].raw_affiliation_string	Institut für Informatik, Universität Tübingen, Tübingen, Germany
authorships[3].institutions[0].id	https://openalex.org/I8087733
authorships[3].institutions[0].ror	https://ror.org/03a1kwz48
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I8087733
authorships[3].institutions[0].country_code	DE
authorships[3].institutions[0].display_name	University of Tübingen
authorships[3].author_position	middle
authorships[3].raw_author_name	Michael Kaufmann
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Institut für Informatik, Universität Tübingen, Tübingen, Germany
authorships[4].author.id	https://openalex.org/A5058217001
authorships[4].author.orcid	https://orcid.org/0000-0003-4089-673X
authorships[4].author.display_name	Sergey Pupyrev
authorships[4].countries	US
authorships[4].affiliations[0].institution_ids	https://openalex.org/I4210099336, https://openalex.org/I4210114444
authorships[4].affiliations[0].raw_affiliation_string	Facebook, Inc., Menlo Park, CA, USA
authorships[4].institutions[0].id	https://openalex.org/I4210099336
authorships[4].institutions[0].ror	https://ror.org/01240pn49
authorships[4].institutions[0].type	education
authorships[4].institutions[0].lineage	https://openalex.org/I4210099336
authorships[4].institutions[0].country_code	US
authorships[4].institutions[0].display_name	Menlo School
authorships[4].institutions[1].id	https://openalex.org/I4210114444
authorships[4].institutions[1].ror	https://ror.org/01zbnvs85
authorships[4].institutions[1].type	company
authorships[4].institutions[1].lineage	https://openalex.org/I4210114444
authorships[4].institutions[1].country_code	US
authorships[4].institutions[1].display_name	Meta (United States)
authorships[4].author_position	last
authorships[4].raw_author_name	Sergey Pupyrev
authorships[4].is_corresponding	False
authorships[4].raw_affiliation_strings	Facebook, Inc., Menlo Park, CA, USA
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Lazy Queue Layouts of Posets
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9994000196456909
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2350741829, https://openalex.org/W2530322880
cited_by_count	2
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2020
counts_by_year[1].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.1007/s00453-022-01067-y
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S89324355
best_oa_location.source.issn	0178-4617, 1432-0541
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	0178-4617
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Algorithmica
best_oa_location.source.host_organization	https://openalex.org/P4310319900
best_oa_location.source.host_organization_name	Springer Science+Business Media
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
best_oa_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Algorithmica
best_oa_location.landing_page_url	https://doi.org/10.1007/s00453-022-01067-y
primary_location.id	doi:10.1007/s00453-022-01067-y
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S89324355
primary_location.source.issn	0178-4617, 1432-0541
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	0178-4617
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Algorithmica
primary_location.source.host_organization	https://openalex.org/P4310319900
primary_location.source.host_organization_name	Springer Science+Business Media
primary_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
primary_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
primary_location.license	cc-by
primary_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-022-01067-y.pdf
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Algorithmica
primary_location.landing_page_url	https://doi.org/10.1007/s00453-022-01067-y
publication_date	2022-11-28
publication_year	2022
referenced_works	https://openalex.org/W2952673825, https://openalex.org/W2134749372, https://openalex.org/W4254807835, https://openalex.org/W2963977128, https://openalex.org/W2766116208, https://openalex.org/W2972155844, https://openalex.org/W4205758352, https://openalex.org/W2116216196, https://openalex.org/W1970144066, https://openalex.org/W2078050303, https://openalex.org/W4232763292, https://openalex.org/W1999897678, https://openalex.org/W1987216097, https://openalex.org/W2963909391, https://openalex.org/W2963634989, https://openalex.org/W1957150339, https://openalex.org/W3033382536, https://openalex.org/W2964274539, https://openalex.org/W3090082925, https://openalex.org/W2044935944, https://openalex.org/W2889544735, https://openalex.org/W3099097085, https://openalex.org/W2143668983
referenced_works_count	23
abstract_inverted_index..	42, 89, 184
abstract_inverted_index.A	22
abstract_inverted_index.a	145
abstract_inverted_index.w	35, 41, 122
abstract_inverted_index.We	1, 66
abstract_inverted_index.an	93, 132, 142
abstract_inverted_index.at	39, 149
abstract_inverted_index.in	8, 161
abstract_inverted_index.is	125
abstract_inverted_index.of	6, 10, 18, 25, 33, 50, 76, 96, 120, 144, 171
abstract_inverted_index.on	116
abstract_inverted_index.we	140
abstract_inverted_index.$$w	78, 173
abstract_inverted_index.2$$	80, 175
abstract_inverted_index.Our	90
abstract_inverted_index.The	43
abstract_inverted_index.and	27, 68, 130
abstract_inverted_index.for	48, 74, 127, 169
abstract_inverted_index.has	36, 45
abstract_inverted_index.is,	14
abstract_inverted_index.the	3, 15, 117, 128, 135, 167
abstract_inverted_index.via	61
abstract_inverted_index.>	79, 174
abstract_inverted_index.+1$$	98
abstract_inverted_index.been	46
abstract_inverted_index.lazy	63, 71
abstract_inverted_index.most	40
abstract_inverted_index.over	134
abstract_inverted_index.that	13, 30, 147
abstract_inverted_index.Heath	26
abstract_inverted_index.bound	95
abstract_inverted_index.every	31, 162
abstract_inverted_index.least	150
abstract_inverted_index.poset	32, 146
abstract_inverted_index.queue	4, 37, 118
abstract_inverted_index.terms	9
abstract_inverted_index.their	11
abstract_inverted_index.tight	126
abstract_inverted_index.upper	94
abstract_inverted_index.which	124
abstract_inverted_index.width	34, 51, 77, 172
abstract_inverted_index.bound.	138
abstract_inverted_index.extend	67
abstract_inverted_index.linear	64, 72, 163
abstract_inverted_index.number	5, 17, 38, 119
abstract_inverted_index.posets	7, 49, 75, 170
abstract_inverted_index.queues	160
abstract_inverted_index.width,	12
abstract_inverted_index.width-	121
abstract_inverted_index.yields	131
abstract_inverted_index.$$w+1$$	151
abstract_inverted_index.$$w=2$$	52
abstract_inverted_index.analyze	70
abstract_inverted_index.asserts	29
abstract_inverted_index.example	143
abstract_inverted_index.implies	92
abstract_inverted_index.maximum	16
abstract_inverted_index.posets,	123
abstract_inverted_index.provide	141
abstract_inverted_index.thereby	165
abstract_inverted_index.Abstract	0
abstract_inverted_index.Further,	139
abstract_inverted_index.analysis	91
abstract_inverted_index.pairwise	19
abstract_inverted_index.requires	148
abstract_inverted_index.strategy	129
abstract_inverted_index.$$(w-1)^2	97
abstract_inverted_index.<mml:math	53, 81, 99, 152, 176
abstract_inverted_index.Pemmaraju	28
abstract_inverted_index.confirmed	47
abstract_inverted_index.elements.	21
abstract_inverted_index.so-called	62
abstract_inverted_index.<mml:mrow>	55, 83, 101, 103, 154, 178
abstract_inverted_index.<mml:msup>	102
abstract_inverted_index.best-known	137
abstract_inverted_index.conjecture	24, 44, 168
abstract_inverted_index.disproving	166
abstract_inverted_index.extension,	164
abstract_inverted_index.extension.	65
abstract_inverted_index.extensions	73
abstract_inverted_index.previously	136
abstract_inverted_index.thoroughly	69
abstract_inverted_index.</mml:math>	60, 88, 115, 159, 183
abstract_inverted_index.</mml:mrow>	59, 87, 109, 114, 158, 182
abstract_inverted_index.</mml:msup>	111
abstract_inverted_index.improvement	133
abstract_inverted_index.investigate	2
abstract_inverted_index.incomparable	20
abstract_inverted_index.long-standing	23
abstract_inverted_index.<mml:mi>w</mml:mi>	56, 84, 105, 155, 179
abstract_inverted_index.<mml:mn>1</mml:mn>	107, 113, 157
abstract_inverted_index.<mml:mn>2</mml:mn>	58, 86, 110, 181
abstract_inverted_index.<mml:mo>(</mml:mo>	104
abstract_inverted_index.<mml:mo>)</mml:mo>	108
abstract_inverted_index.<mml:mo>+</mml:mo>	112, 156
abstract_inverted_index.<mml:mo>-</mml:mo>	106
abstract_inverted_index.<mml:mo>=</mml:mo>	57
abstract_inverted_index.<mml:mo>></mml:mo>	85, 180
abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML">	54, 82, 100, 153, 177
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
corresponding_author_ids	https://openalex.org/A5006472576
countries_distinct_count	4
institutions_distinct_count	5
corresponding_institution_ids	https://openalex.org/I194019607
citation_normalized_percentile.value	0.44612529
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False