Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
From Graph Transformation Units via MiniSat to GrGen.NET
verfasst von : Marcus Ermler, Hans-Jörg Kreowski, Sabine Kuske, Caroline von Totth
Erschienen in: Applications of Graph Transformations with Industrial Relevance
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In logistics and other application areas, one faces many intractable and NP-hard problems like scheduling, routing, packing, planning, and various kinds of optimization. Many of them can nicely and correctly be modeled by means of graph transformation. But a graph transformation engine fails to run the solutions properly because it does not have any mechanisms to overcome or circumvent the intractability. In this paper, we propose to combine the graph transformation engine GrGen.NET with the SAT solver MiniSat to improve the situation. SAT solvers have proved to run efficiently in many cases in the area of chip design and verification. We want to take these positive experiences up and to use the SAT solver as a tentative experiment for assisting the graph transformation engine in finding solutions to NP-hard problems.