Artikel in Tagungsband INPROC-2015-04

Skouradaki, 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.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik.
S. 1-10, englisch.
IEEE, April 2015.
Artikel in Tagungsband (Konferenz-Beitrag).
CR-Klassif.I.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.

Abteilung(en)Universität Stuttgart, Institut für Architektur von Anwendungssystemen
Projekt(e)BenchFlow LE2275/7-1
Eingabedatum13. Januar 2015
   Publ. Institut   Publ. Informatik