CVSM Bibliography, Entry [ Uh2008CVSM ]

Uhrig, Sabrina: Matching Class Diagrams: With Estimated Costs Towards The Exact Solution?;
p.7-12 in: Proc. 2008 ICSE Workshop on Comparison and Versioning of Software Models, May 17, 2008, Leipzig; ACM; 2008
Library Entries: ACM Digital Library
Deskriptoren: CVSM08, CVSM

Abstract: It is widely known that the general matching problem on graphs is a non-polynomial optimization problem. Thus all differencing algorithms we know of use heuristics to identify corresponding elements (e.g.[2],[6]) apart from those that rely on unique identifiers (e.g.[5],[3]). We wonder if an exact algorithm can be designed which computes a minimal cost matching between the elements of the class diagrams and which, although it shows a non-polynomial worst case behaviour, delivers its solution much faster in most cases. In this position paper we describe our ongoing work, the idea of an algorithm which works with estimated transformation costs in order to reduce the computation costs. The algorithm has not been implemented yet; it has only been manually tested on a few examples.