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

complexitymonotone multi-dimensional arraypartially ordered setsearch algorithm

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

(3)

• On the optimality of tape merge of two lists with similar size
• scientific article; zbMATH DE number 7120968 (Why is no real title available?)
• An analysis of Las Vegas algorithms for linear search

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)