NLC-Weite

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 | Quelltext 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

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 .

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 | Quelltext 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 | Quelltext bearbeiten]

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

  • 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 | Quelltext bearbeiten]
  1. Egon Wanke: k-NLC Graphs and Polynomial Algorithms, Discrete Applied Mathematics, 54:251-266, 1994