Dividing and conquering the square

Donna C. Llewellyn, Craig A. Tovey

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

A local minimum of a matrix is a cell whose value is smaller than those of its four adjacent cells. For an n × n square matrix, we find a local minimum with at most 2.554n queries, and prove a lower bound of 2n queries required by any method. For a different neighborhood corresponding to the eight possible moves of a chess king, we prove upper and lower bounds of3n + O(log n) and 2n, respectively.

Original languageEnglish
Pages (from-to)131-153
Number of pages23
JournalDiscrete Applied Mathematics
Volume43
Issue number2
DOIs
StatePublished - 19 May 1993

Keywords

  • Local optimum
  • graph
  • grid
  • local search
  • matrix
  • saddle point

Fingerprint

Dive into the research topics of 'Dividing and conquering the square'. Together they form a unique fingerprint.

Cite this