Twin Width

Die Twin Width (englisch für „Zwillingsweite“) eines ungerichteten Graphen ist eine natürliche Zahl, die angibt, wie ähnlich der gegebene Graph zu einem Co-Graphen ist. Ein Co-Graph ist ein Graph, der mittels wiederholter Verschmelzung von Zwillingen, das sind Knoten mit identischer Nachbarschaft, zu einem einzelnen Knoten reduziert werden kann. Die Twin Width ist durch eine Folge von wiederholtem Verschmelzen der Knoten definiert, die zwar keine Zwillinge sind, aber eine ähnliche Nachbarschaft aufweisen.

Definition

Die Twin Width ist für einen endlichen ungerichtete Graphen $G=(V,E)$ definiert. Dieser verfügt über eine endliche Menge an Knoten $V$, und eine Menge an Kanten $E$, die ungeordnete Paare von Knoten sind. Die Zwillingsweite ist der minimale Knotengrad $d$ der roten Kanten in einer Kontraktionsfolge.

Literatur

• Vorlage:Cite journal
• Vorlage:Cite journal

• Vorlage:Cite conference