Fully Dynamic Evaluation of Sequence Pair

2013

In the electronic design automation field, as well as in other areas, problem instances and solutions are often subject to discrete changes. The foundational significance of efficient updates of the criterion value after dynamic updates, instead of recomputing it from scratch each time, has attracted a lot of research. In this paper, motivated by the significance of the sequence pair (SP) representation for floorplanning, we develop a fully dynamic algorithm of SP evaluation, that efficiently updates a criterion value after insertions and deletions of SP elements and after modifications of element weights. Our result is based on a new data structure for the predecessor problem, which mainta…