Für die eigentliche Abdeckung erfolgt eine Dekomposition der Schaltung in eine kanonische Darstellung mit Basisfunktionen (z.B. NAND-, NOR-Gatter mit 2 Eingängen und Invertern) für den DAG (Subject Graph genannt) und die Bibliothek (Pattern Graph genannt). Da die Bibliothek in der Regel auch diese Basisfunktionen enthält, gibt es mindestens eine triviale Abdeckung. Ziel ist es jedoch durch Verwendung komplexer Zellen der Bibliothek (Komplexgatter), z.B. Gatter mit mehr als zwei Eingängen, eine flächengünstigere Lösung zu finden.
Der Lösungsraum für die Abdeckung wird durch die Partitionierung und die Dekomposition eingeschränkt. Die Lösung erfolgt in zwei Schritten mit einem dynamischen Algorithmus:
Matching mit Optimierung
Für alle Teilbäume eines Baums wird eine Liste mit allen möglichen Matchings erstellt.
D.h. Teilbäume des Subject Graphs werden durch isomorphe Pattern Graphs ersetzt.
Dies ist ein rekursives Bottom-Up-Verfahren,
das das optimale Matching für jeden Teilbaum findet. Dabei wird von den Eingängen
des Subject Graphs schrittweise zu den Ausgängen vorgegangen.
Für jede zugeordnete Zelle eines Knotens des Baums werden die Kosten der Zelle
und der optimalen Matchings der Eingänge dieser Zelle berechnet.
Am Ende wird das optimale Matching an der Wurzel des Baums bestimmt (Matching mit
den niedrigsten Kosten).
Akkumulation
Hier werden in einem Top-Down-Verfahren die Ergebnisse der Optimierung genutzt,
um eine Abdeckung des gesamten Baums zu erzielen.
Ausgehend von der optimalen Zelle der Wurzel des Baumes, werden rekursiv die Teilbäume
der Eingänge der zugeordneten Zelle zugeordnet.