A new strategy for generating shortest addition sequences |
| |
Authors: | Hatem M Bahig Hazem M Bahig |
| |
Affiliation: | 1.Computer Science Division, Department of Mathematics, Faculty of Science,Ain Shams University,Cairo,Egypt |
| |
Abstract: | An addition sequence problem is given a set of numbers X = {n 1, n 2, . . . , n m }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n j , 1 ≤ j ≤ m, in the search tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|