Fast evaluation of sequence pair in block placement by longest common subsequence computation

Xiaoping Tang, Ruiqi Tian, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

72 Citations (Scopus)

Abstract

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e. to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O(n log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.
Original languageEnglish
Title of host publicationProceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2000
EditorsPeter Marwedel
PublisherIEEE
Pages106-111
Number of pages6
ISBN (Print)0769505376
DOIs
Publication statusPublished - 27 Mar 2000
Event2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000 - Paris, France
Duration: 27 Mar 200030 Mar 2000
https://ieeexplore.ieee.org/xpl/conhome/6761/proceeding (Conference proceedings)
https://dl.acm.org/doi/proceedings/10.1145/343647 (Conference proceedings)

Publication series

NameProceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE

Conference

Conference2000 Design, Automation and Test in Europe Conference and Exhibition, DATE 2000
Country/TerritoryFrance
CityParis
Period27/03/0030/03/00
Internet address

Fingerprint

Dive into the research topics of 'Fast evaluation of sequence pair in block placement by longest common subsequence computation'. Together they form a unique fingerprint.

Cite this