  Since the birth of web service composition, minimizing the number of web
services of the resulting composition while satisfying the user request has
been a significant perspective of research. With the increase of the number of
services released across the Internet, seeking efficient algorithms for this
research is an urgent need. In this paper we present an efficient mechanism to
solve the problem of web service composition. For the given request, a service
dependency graph is firstly generated with the relevant services picked from an
external repository. Then, each search step on the graph is transformed into a
dynamic knapsack problem by mapping services to items whose volume and cost is
changeable, after which a knapsack-variant algorithm is applied to solve each
problem after transformation. Once the last search step is completed, the
minimal composition that satisfies the request can be obtained. Experiments on
eight public datasets proposed for the Web Service Challenge 2008 shows that
the proposed mechanism outperforms the state-of-the-art ones by generating
solutions containing the same or smaller number of services with much higher
efficiency.
