The online house numbering problem: min-max online list labeling

DOI10.4230/LIPICS.ESA.2017.33MaRDI QIDQ5111720zbMATH OpenOpenAlexFDO

Authors William E. Devanny, Jeremy T. Fineman, Tsvi Kopelowitz, Michael T. Goodrich

Publication date 27 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2017.html#DevannyFGK17

zbMATH Keywords

list labelingfile maintenancehouse numbering

Mathematics Subject Classification ID

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

Recommendations

• Online labeling: algorithms, lower bounds and open questions
• Minimal on-line labelling
• On Online Labeling with Polynomially Many Labels
• A tight lower bound for on-line monotonic list labeling
• A Tight Lower Bound for Online Monotonic List Labeling

Cites work

• scientific article; zbMATH DE number 432808 (Why is no real title available?)
• scientific article; zbMATH DE number 140460 (Why is no real title available?)
• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• A locality-preserving cache-oblivious dynamic dictionary
• Cache-Oblivious B-Trees
• Competitive Analysis of Flash-Memory Algorithms
• Cross-document pattern matching
• Dynamic LCA Queries on Trees
• File maintenance: when in doubt, change the layout!
• Improved dynamic dictionary matching
• Managing unbounded-length keys in comparison-driven data structures with applications to online indexing
• Near real-time suffix tree construction via the fringe marked ancestor problem
• New bounds for the controller problem
• On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Sparsification—a technique for speeding up dynamic graph algorithms
• Tight lower bounds for the online labeling problem
• Wear minimization for cuckoo hashing: how not to throw a lot of eggs into one basket

Cited in

(1)

• Online list labeling: breaking the ^2n barrier

This page was built for publication: The online house numbering problem: min-max online list labeling

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