Sparse dominance queries for many points in optimal time and space

DOI10.1016/S0020-0190(97)00181-6MaRDI QIDQ293151zbMATH OpenOpenAlexFDO

Authors T. Graf, V. Kamakoti

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001816?np=y

zbMATH Keywords

dominating pointinterval treelayered witness graphpriority search tree

Mathematics Subject Classification ID

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

Recommendations

• A metric approach to sparse domination
• Efficient enumeration of dominating sets for sparse graphs
• Efficient enumeration of dominating sets for sparse graphs
• Some remarks on the pointwise sparse domination
• FPT algorithms for domination in sparse graphs and beyond
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Space-Time Trade-Offs for Orthogonal Range Queries
• Sparse sets, approximable sets, and parallel queries to NP
• scientific article; zbMATH DE number 1304328

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Making data structures persistent
• Priority Search Trees

This page was built for publication: Sparse dominance queries for many points in optimal time and space

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