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.