An efficient data structure for maxplus merge in dynamic programming

Chen Ruiming; Zhou Hai

doi:10.1109/TCAD.2006.882479

An efficient data structure for maxplus merge in dynamic programming

Chen Ruiming^*, Zhou Hai

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	3004-3009
Number of pages	6
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	25
Issue number	12
DOIs	https://doi.org/10.1109/TCAD.2006.882479
State	Published - Dec 2006

Keywords

Data structure
Dynamic programming
Timing optimization

ASJC Scopus subject areas

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

Access to Document

10.1109/TCAD.2006.882479

Cite this

@article{8e2a4eaf927c40b7a204ddaf173a6080,

title = "An efficient data structure for maxplus merge in dynamic programming",

abstract = "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.",

keywords = "Data structure, Dynamic programming, Timing optimization",

author = "Chen Ruiming and Zhou Hai",

year = "2006",

month = dec,

doi = "10.1109/TCAD.2006.882479",

language = "English (US)",

volume = "25",

pages = "3004--3009",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

TY - JOUR

T1 - An efficient data structure for maxplus merge in dynamic programming

AU - Ruiming, Chen

AU - Hai, Zhou

PY - 2006/12

Y1 - 2006/12

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

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

KW - Data structure

KW - Dynamic programming

KW - Timing optimization

UR - http://www.scopus.com/inward/record.url?scp=33845659614&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845659614&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2006.882479

DO - 10.1109/TCAD.2006.882479

M3 - Article

AN - SCOPUS:33845659614

SN - 0278-0070

VL - 25

SP - 3004

EP - 3009

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 12

ER -

An efficient data structure for maxplus merge in dynamic programming

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this