Lower bounds for monotonic list labeling

DOI10.1007/3-540-52846-6_87MaRDI QIDQ5056101zbMATH OpenOpenAlexFDO

Authors Ju Zhang, Paul F. Dietz

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_87

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A tight lower bound for on-line monotonic list labeling
• A Tight Lower Bound for Online Monotonic List Labeling
• Higher lower bounds on monotone size
• A method for obtaining efficient lower bounds for monotone complexity
• Lower bounds for linear decision lists
• scientific article; zbMATH DE number 1383704
• A lower bound for the complexity of monotone graph properties
• Lower bounds for monotone counting circuits
• Tight lower bounds for list edge coloring
• Lower bounds for monotone span programs

Cites work

• Amortized Computational Complexity
• Controlled density sorting
• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• scientific article; zbMATH DE number 140460 (Why is no real title available?)
• Maintaining order in a generalized linked list
• Making data structures persistent
• Padded Lists Revisited

Cited in

(7)

• Canonical density control
• Tight lower bounds for the online labeling problem
• Binary search trees: How low can you go?
• A tight lower bound for on-line monotonic list labeling
• On online labeling with large label set
• A Tight Lower Bound for Online Monotonic List Labeling
• Online list labeling: breaking the ^2n barrier

This page was built for publication: Lower bounds for monotonic list labeling

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