Inzidenz-Treewidth

- Natural & Formal Sciences -
Mathematics & Logic Dictionary
Der Treewidth des Inzidenzgraphen einer logischen Formel oder CNF-Instanz: Der Inzidenzgraph hat einen Knoten für jede Variable und jede Klausel und Kanten zwischen einer Variable und jeder Klausel, die sie enthält; Inzidenz-Treewidth misst, wie baumartig diese bipartite Struktur ist.