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

Bearbeiten

Der Begriff der NLC-Weite wurde von 1994 von Wanke eingeführt[1]. Für die Definition der NLC-Weite ist der Begriff des k-markierten Graphen wichtig:

k-markierter Graph

Bearbeiten
  • 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

Bearbeiten

Die NLC-Weite eines k-markierten Graphen   ist die kleinste natürliche Zahl   sodass   in der Graphklasse   liegt.

Dabei ist   wie folgt rekursiv definiert:

  1. Der  -markierte Graph   ist für ein   in  
  2. Seien   und   in  . Weiterhin seien   und   knotendisjunkt und   eine Relation. Dann ist auch der  -markierte Graph
     
    in  , mit
     ,
      und
     
    für alle  .
  3. Seien   ein  -markierter Graph und   eine totale Funktion. Dann ist auch der  -markierte Graph
     
    in   mit  .

Beispiel

Bearbeiten

Die nachfolgende Tabelle demonstriert die Konstruktion des "Haus vom Nikolaus"-Graphen mithilfe der oben definierten Operationen:

NLC-Operation Darstellung des Graphen
   
   
   
   
   

Es gilt somit  .   hat weiterhin eine NLC-Weite von 1, da   ein Co-Graph ist.

NLC-Weite spezieller Graphklassen

Bearbeiten

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

Bearbeiten

Für jeden ungerichteten Graphen   mit NLC-Weite   und Cliquenweite   gilt:

 

Literatur

Bearbeiten
  • 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

Bearbeiten
  1. Egon Wanke: k-NLC Graphs and Polynomial Algorithms, Discrete Applied Mathematics, 54:251-266, 1994