An efficient data structure for maxplus merge in dynamic programming

Chen Ruiming*, Zhou Hai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Dynamic programming is a useful technique to handle slicing floorplan, technology mapping, and buffering problems, where many maxplus merge operations of solution lists are needed. Shi proposed an efficient O(n log n) time algorithm to speed up the merge operation. Based on balanced binary search trees, his algorithm showed superb performance with the most unbalanced sizes of merging solution lists. The authors propose in this paper a more efficient data structure for the merge operations. With parameters to adjust adaptively, their algorithm works better than Shi's under all cases, unbalanced, balanced, and mix sizes. Their data structure is also simpler.

Original languageEnglish (US)
Pages (from-to)3004-3009
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
StatePublished - Dec 2006


  • Data structure
  • Dynamic programming
  • Timing optimization

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'An efficient data structure for maxplus merge in dynamic programming'. Together they form a unique fingerprint.

Cite this