Searching monotone multi-dimensional arrays

DOI10.1016/J.DISC.2007.04.067zbMATH Open1147.68469arXivcs/0504026OpenAlexW2075018862MaRDI QIDQ2483400FDOQ2483400

Authors: Yongxi Cheng, Xiaoming Sun, Yiqun Lisa Yin 

Publication date: 28 April 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

zbMATH Keywords

complexitypartially ordered setsearch algorithmmonotone multi-dimensional array

Mathematics Subject Classification ID

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

Cites Work

• Searching ordered structures
• Every poset has a central element

Cited In (2)

• Title not available (Why is that?)
• 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)