Searching monotone multi-dimensional arrays

DOI10.1016/J.DISC.2007.04.067MaRDI QIDQ2483400zbMATH OpenOpenAlexFDO

Authors Yongxi Cheng, Xiaoming Sun, Yiqun Lisa Yin

Publication date 28 April 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0504026

zbMATH Keywords

complexitypartially ordered setsearch algorithmmonotone multi-dimensional array

Mathematics Subject Classification ID

Partial orders, general (06A06) Searching and sorting (68P10)

Abstract: In this paper we investigate the problem of searching monotone multi-dimensional arrays. We generalize Linial and Saks' search algorithm cite{LS1} for monotone 3-dimensional arrays to $d$-dimensions with $dgeq4$. Our new search algorithm is asymptotically optimal for $d=4$.

Recommendations

• Recognition of \(d\)-dimensional Monge arrays
• Selection and sorting in totally monotone arrays
• scientific article; zbMATH DE number 4072395
• Parallel searching of multidimensional cubes
• IMPROVED SELECTION IN TOTALLY MONOTONE ARRAYS

Cites work

• Every poset has a central element
• Searching ordered structures

Cited in

(2)

• scientific article; zbMATH DE number 7120968 (Why is no real title available?)
• On the optimality of tape merge of two lists with similar size

This page was built for publication: Searching monotone multi-dimensional arrays

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