Graph Theory and Model Collection Management – Conceptual Framework and Runtime Analysis of Selected Graph Algorithms

Breuker Dominic, Delfmann Patrick, Dietrich Hanns-Alexander, Steinhorst Matthias

Abstract

Analysing conceptual models is a frequent task of Business Process Management (BPM). Application scenarios include comparing or integrating business processes, checking business processes for compliance or weaknesses, and customizing conceptual models for different audiences. Many companies maintain large model collections. Analysing such collections manually can be laborious. Hence, practitioners have articulated demand for (semi-)automatic support. BPM scholars address this demand with a plethora of different model analysis techniques. As most conceptual models can be interpreted as mathematical graphs and model analysis techniques often include some kind of graph problem, we introduce a model analysis framework based on graph algorithms. These algorithms are supposed to be used as building blocks in higher-level model analysis techniques. To prove that graph algorithms are applicable in this domain, we conduct a performance analysis of selected algorithms.