Baumweite

Def: die Baumweite (tree width):

tw(G) : = min{k | G ist partieller k-Baum}

leider ... TW = {(G, k) | tw(G)$\le$k} $\in$ NPC,

aber ...für jedes feste k : TW_k = {G | tw(G)$\le$k} $\in$ P (sogar Linearzeit, aber mit abenteuerlichen Faktoren)

Die Algorithmen zur nachträglichen Feststellung der Baumweite bzw. eines Eliminationsschemas sind unpraktisch ... aber oft gar nicht nötig: in vielen Anwendungen kann man ein Eliminationsschema schon von vornherein in der Eingabe des Algorithmus voraussetzen, z. B. für Graphen, die durch die Art ihrer Erzeugung (also genetisch) kleine Baumweite haben.