Re: [henshin-dev] [henshin-user] Complexity of the method InterpreterUti

[Christian Krause <henshin.ck@xxxxxxxxx>]

Hello Svetlana,

the pattern matcher is based on an encoding into constraint satisfaction problems. It's run-time highly depends on the pattern and the input graph. Therefore giving sharp bounds for the complexity is very difficult. Most of the ideas underlying the pattern matcher have been described in this paper: http://link.springer.com/chapter/10.1007/978-3-540-46464-8_17

Additionally, Henshin tries to use things like opposite edges, path constraints and parallelization to speed up the match finding.

Cheers,

Christian

2015-10-03 14:59 GMT+02:00 Svetlana Arifulina <svetlana.arifulina@xxxxxxxxxxxxxxxx>:

Hello Henshin developers and Henshin users,

my name is Svetlana and I use the graph matching of Henshin in my PhD Thesis. For my research, I would like to know if there are any papers published, in which the complexity of the method findAllMatches of InterpreterUtil is estimated?

Thank you in advance.

Best regards

Svetlana Arifulina
_______________________________________________
henshin-user mailing list
henshin-user@xxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://dev.eclipse.org/mailman/listinfo/henshin-user