中文摘要：

为提升自动服务组合效率，提出在新的服务图结构中实现线性服务组合。该方法使用有向带环加权多图描述服务关系。在深度与广度搜索相结合的组合路径查找过程中，基于语义包容关系将图中节点对之间的多边降级为单边。通过着色和时间戳判断、消除环。给出了具有线性时间复杂度的组合路径查找算法并对其时间复杂度予以理论证明。仿真结果表明：与同类方法相比，该方法能够在线性时间内，在不降低查全率的情况下，发现带环图中的组合路径，并具有查找时间与服务图规模无关的良好可扩展性。

英文摘要：

To promote the efficiency of automatic service composition, a linear service composition realization is proposed in a new service graph structure. The service relationship is modeled as a directed cyclic weighted multi-graph. In the searching process of composition paths combining depth- first traveling and breadth-first traveling, the multi-edges of node pairs are degraded to uni-edges based on semantic subsumption. Cycles are discovered and eliminated via both coloring and timing stamp. A composition path searching algorithm with linear time complexity is presented and theoretically demon- strated. The simulation results prove：compared with other similar methods, this method can find combination paths in cyclic graphs with linear time complexity without loss of the ratio of recall, and has good expansibility that the searching time is independent with scales of servicing graphs.