Twin Width

natürliche Zahl die angibt, wie ähnlich der gegebene Graph zu einem zu einem Co-Graphen ist

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

Bearbeiten

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

Literatur

Bearbeiten
  • Pierre Bergé, Édouard Bonnet, Hugues Bonnet, Rémi Watrigant: Approximating highly inapproximable problems on graphs of bounded twin-width. 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany. Band 254, LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, S. 10:1–10:15, doi:10.4230/LIPIcs.STACS.2023.10, arxiv:2207.07708 (englisch).