Online labeling: algorithms, lower bounds and open questions

DOI10.1007/978-3-319-90530-3_3zbMATH Open1484.68344OpenAlexW2799887281MaRDI QIDQ1625136FDOQ1625136

Authors: Michael Saks 

Publication date: 28 November 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-90530-3_3

Recommendations

• Tight lower bounds for the online labeling problem
• Tight lower bounds for the online labeling problem
• On Online Labeling with Polynomially Many Labels
• On randomized online labeling with polynomially many labels
• On online labeling with large label set
• A Tight Lower Bound for Online Monotonic List Labeling
• scientific article; zbMATH DE number 7364985
• Online lower bounds via duality
• A tight lower bound for on-line monotonic list labeling
• Lower bounds for online bin covering-type problems

zbMATH Keywords

data structuresonline labeling

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Data structures (68P05)

Cited In (9)

• A tight lower bound for on-line monotonic list labeling
• An Optimal Algorithm for Online Freeze-tag
• Tight lower bounds for the online labeling problem
• Tight lower bounds for the online labeling problem
• On randomized online labeling with polynomially many labels
• On online labeling with large label set
• The online house numbering problem: min-max online list labeling
• On Online Labeling with Polynomially Many Labels
• A Tight Lower Bound for Online Monotonic List Labeling

This page was built for publication: Online labeling: algorithms, lower bounds and open questions

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