Article in Proceedings INPROC-2015-04

BibliographySkouradaki, Marigianna; Goerlach, Katharina; Hahn, Michael; Leymann, Frank: Application of Sub-Graph Isomorphism to Extract Reoccurring Structures from BPMN 2.0 Process Models.
In: 9th International IEEE Symposium on Service-Oriented System Engineering : SOSE 2015; San Francisco Bay, USA, March 30 - 3, 2015.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 1-10, english.
IEEE, April 2015.
Article in Proceedings (Conference Paper).
CR-SchemaI.2.8 (Problem Solving, Control Methods, and Search)
F.2.2 (Nonnumerical Algorithms and Problems)
D.2.9 (Software Engineering Management)
Keywordsstructural similarities; process models; BPMN 2.0; process fragments; subgraph isomorphism

The state-of-art approaches in structural similarities of process models base their operations on behavioral data and text semantics. These data is usually missing from mock-up or obfuscated process models. This fact makes it complicated to apply current approaches on these types of models. We examine the problem of the automated detection of re-occurring structures in a collection of process models, when text semantics or behavioral data are missing. This problem is a case of (sub)graph isomorphism, which is mentioned as NP-complete in the literature. Since the process models are very special types of attributed directed graphs we are able to develop an approach that runs with logarithmic complexity. In this work we set the theoretical basis, develop a configurable approach for the detection of re-occurring structures in any process models collection, and validate it against a set of BPMN 2.0 models. We define two execution scenarios and discuss the relation of the execution times with the complexity of the comparisons. Finally, we analyze the detected structures, and propose the configurations that lead to optimal results.

Department(s)University of Stuttgart, Institute of Architecture of Application Systems
Project(s)BenchFlow LE2275/7-1
Entry dateJanuary 13, 2015
   Publ. Institute   Publ. Computer Science