An optimal and fast algorithm for web service composition

Automatic composition is not a trivial problem, especially when the number of services is high and there are different control structures to handle the execution flow. In this paper, we present an A* algorithm for automatic service composition that obtains all valid compositions from a extended service dependency graph, using different control structures (sequence, split, choice). A full experimental validation with eight different public repositories has been done, showing a great performance as the algorithm found all valid compositions in a short period of time.

keywords: Heuristic search, A* algorithm, Web services composition