An optimal and fast algorithm for web service composition

Abstract. Automatic composition is not a trivial problem, especially when the number of services is high and there are different control struc-tures to handle the execution flow. In this paper, we present an A * algo-rithm for automatic service composition that obtains all valid composi-tions 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 perfor-mance as the algorithm found all valid compositions in a short period of time