Die NLC-Weite ist ein Begriff aus der Graphentheorie und weist jedem ungerichteten Graphen eine natürliche Zahl zu. Auf Graphen mit beschränkter NLC-Weite lassen sich bestimmte schwere Probleme wie zum Beispiel MAX-CUT oder das Hamiltonkreisproblem in polynomieller Zeit lösen.
Definition Der Begriff der NLC-Weite wurde von 1994 von Wanke eingeführtEgon Wanke: k-NLC Graphs and Polynomial Algorithms, Discrete Applied Mathematics, 54:251-266, 1994. Für die Definition der NLC-Weite ist der Begriff des k-markierten Graphen wichtig:
k-markierter Graph Für ein sei Ein k-markierter Graph ist ein Graph , dessen Knoten mit einer Markierungsabbildung markiert werden Ein Graph mit genau einem mit markierten Knoten wird mit bezeichnet
Definition Die NLC-Weite eines k-markierten Graphen ist die kleinste natürliche Zahl sodass in der Graphklasse liegt.
Dabei ist wie folgt rekursiv definiert:
Der -markierte Graph ist für ein in Seien und in . Weiterhin seien und knotendisjunkt und eine Relation. Dann ist auch der -markierte Graph
in , mit , und
für alle . Seien ein -markierter Graph und eine totale Funktion. Dann ist auch der -markierte Graph
in mit .
Beispiel Die nachfolgende Tabelle demonstriert die Konstruktion des "Haus vom Nikolaus"-Graphen mithilfe der oben definierten Operationen:
NLC-Operation Darstellung des Graphen 150px 150px 150px 150px 150px
Es gilt somit . hat weiterhin eine NLC-Weite von 1, da ein Co-Graph ist.
NLC-Weite spezieller Graphklassen
Die NLC-Weiten der folgenden Graphklassen lassen sich wie folgt nach oben abschätzen:
Jeder Co-Graph hat eine NLC-Weite von 1 Bäume haben eine NLC-Weite von höchstens 3 Kreise haben eine NLC-Weite von höchstens 4
Zusammenhang zur Cliquenweite Für jeden ungerichteten Graphen mit NLC-Weite und Cliquenweite gilt:
Literatur Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1
Einzelnachweise
Kategorie:Graphentheorie