A new strategy for generating shortest addition sequences
Bahig, Hazem;
Abstract
An addition sequence problem is given a set of numbers X = {n1, n2, . . . , nm}, 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.
Other data
| Title | A new strategy for generating shortest addition sequences | Authors | Bahig, Hazem | Keywords | addition sequences; branch-and-bound, shortest sequence | Issue Date | 1-Mar-2011 | Publisher | SPRINGER WIEN | Journal | Computing (Vienna/New York) | DOI | 285 3 306 https://api.elsevier.com/content/abstract/scopus_id/79958266555 91 10.1007/s00607-010-0119-7 |
Scopus ID | 2-s2.0-79958266555 | Web of science ID | WOS:000288169700004 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.