A Tight Lower Bound for Online Monotonic List Labeling

DOI10.1137/S0895480100315808MaRDI QIDQ5317575zbMATH OpenFDO

Authors Joel I. Seiferas, Ju Zhang, Paul F. Dietz

Publication date 16 September 2005

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480100315808

zbMATH Keywords

adversary argumentbucketingdensity/congestion management and exploitationload balancinglower boundmonotonic list labelingonlineorder maintenance

Mathematics Subject Classification ID

Data structures (68P05) Discrete mathematics in relation to computer science (68R99)

Recommendations

• A tight lower bound for on-line monotonic list labeling
• Lower bounds for monotonic list labeling
• On online labeling with large label set
• On Online Labeling with Polynomially Many Labels
• Online labeling: algorithms, lower bounds and open questions

Cited in

(10)

• Online labeling: algorithms, lower bounds and open questions
• On Online Labeling with Polynomially Many Labels
• Tight lower bounds for the online labeling problem
• Lower bounds for monotonic list labeling
• A tight lower bound for on-line monotonic list labeling
• The online house numbering problem: min-max online list labeling
• On online labeling with large label set
• New bounds for the controller problem
• Online list labeling: breaking the ^2n barrier
• Minimal on-line labelling

This page was built for publication: A Tight Lower Bound for Online Monotonic List Labeling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317575)